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.
Given a level-order binary tree with None holes, return totalSum, maxPathSum, and maxPathNodes for the best root-to-leaf path. Ties prefer left-to-right traversal.
Constraints
- Inputs are provided as Python literals compatible with the function signature.
- Return a deterministic value exactly matching the requested output.
Examples
Input: ([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1],)
Expected Output: {'totalSum': 55, 'maxPathSum': 27, 'maxPathNodes': [5, 4, 11, 7]}
Explanation: Mixed tree.
Input: ([],)
Expected Output: {'totalSum': 0, 'maxPathSum': 0, 'maxPathNodes': []}
Explanation: Empty tree.
Input: ([-10, 9, 20, None, None, 15, 7],)
Expected Output: {'totalSum': 41, 'maxPathSum': 25, 'maxPathNodes': [-10, 20, 15]}
Explanation: Negative root.
Hints
- Start with a direct data structure representation.
- Handle edge cases before the main loop.