Compute sums and maximum path in a tree
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given a binary tree whose nodes store integer values. You must implement your own `Node` class (e.g., `val`, `left`, `right`).
## Task
Write a function that, given the root node, computes all of the following:
1. **Total sum**: the sum of values of **all** nodes in the tree.
2. **Maximum path value**: the maximum possible sum of values along a **simple path** in the tree, where a path:
- can start and end at **any** two nodes,
- must follow parent-child links,
- cannot visit a node more than once.
3. **Nodes on a maximum path**: return one valid path (as a list of node values, or node references) that achieves the maximum path value.
## Input / Output
- **Input:** `root` (or `null` for an empty tree).
- **Output:** a structure/tuple like `(totalSum, maxPathSum, maxPathNodes)`.
## Constraints (assume)
- `0 <= number of nodes <= 2e5`
- Node values are integers (may be negative).
## Notes
- If the tree is empty, define `totalSum = 0`, `maxPathSum = 0`, and `maxPathNodes = []`.
- If multiple maximum paths exist, returning any one is acceptable.
Quick Answer: This question evaluates understanding and implementation of binary tree traversal, recursion, aggregation of node values, and computation of maximum simple-path sums, measuring competency in data structures and algorithmic problem-solving within the Coding & Algorithms domain.