Problem
A path is any sequence of nodes connected by edges where each node appears at most once; it need not pass through the root. Return the largest possible sum of node values along any non-empty path. Node values may be negative.
Worked examples
Input: root = [1,2,3]
Output: 6
The path 2 -> 1 -> 3 sums to 6.
Input: root = [-10,9,20,null,null,15,7]
Output: 42
The path 15 -> 20 -> 7 sums to 42; including -10 would only hurt.
Hints
Hint 1
This is the diameter idea with sums instead of edge counts.
Hint 2
A path can bend at one node, but what you report upward to a parent must be a single downward branch.
Hint 3
A branch with a negative sum is better dropped, so clamp child gains at 0.
Solution approach
- Define gain(node) as the best sum of a downward path starting at node. Compute left = max(gain(left), 0) and right = max(gain(right), 0). The best path bending at this node is val + left + right, so update a global maximum with it. Return val + max(left, right) to the parent, since a parent can only extend one branch. Initialize the global maximum to negative infinity so all-negative trees work.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n) time; O(h) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗