Binary Tree Maximum Path Sum
Problem Statement
A path in a binary tree is any sequence of connected nodes where each adjacent pair has a parent-child edge, and a node can appear at most once. The path does not need to pass through the root. Given the root of a non-empty binary tree, return the maximum possible path sum.
Input
The root pointer of a non-empty binary tree.
Output
An integer: the largest sum over any valid connected path in the tree.
Constraints
- •
1 <= number of nodes <= 3 * 10^4 - •
-1000 <= Node.val <= 1000
Examples
Example 1
root = [1,2,3]
6Example 2
root = [-10,9,20,null,null,15,7]
42Example 3
root = [-3]
-3Learning Objectives
- Distinguish the downward gain returned to a parent from the bent path considered for the global answer.
- Clamp negative child gains to **0** so harmful branches are not included.
- Use postorder recursion to combine subtree gains after both children are solved.
- Handle all-negative trees by initialising the global best below every possible node value.
Intuition
Pattern Recognition
The signal is a tree path problem where the best path may start and end anywhere, and may bend through a node. This is the hard version of the same template as diameter: return one value up, track a global best. The parent can only extend a single downward chain from a child, but the answer at the current node may use both children and bend through the node.
The crucial distinction is return-value versus global-best. Return the best downward gain: node.val plus the better child gain, because the parent can attach to only one side. Update the global best with the bent path node.val + leftGain + rightGain. If a child gain is negative, clamp it to 0 because choosing that branch would only make the path worse.
Common mistakes
- ×Returning a path that uses both left and right children, which cannot be extended by the parent.
- ×Forgetting to clamp negative gains to **0**, causing harmful branches to reduce good paths.
- ×Initialising the global best to **0**, which fails when every node value is negative.
- ×Assuming the best path must include the root.
Algorithm Explanation
Key idea
For each node, compute the best downward gain from its left child and right child. Clamp each gain with max(0, childGain) because a negative branch is better ignored. The path that bends through the current node is node.val + leftGain + rightGain; use it to update a global best. The value returned upward is node.val + max(leftGain, rightGain), because a parent can continue through only one child branch.
Recursion walkthrough
For [-10,9,20,null,null,15,7], leaf 9 has left gain 0 and right gain 0. It updates the global best to 9 and returns downward gain 9. Leaf 15 updates the global best to 15 and returns 15. Leaf 7 returns 7, while the global best remains 15.
At node 20, the left gain is 15 and the right gain is 7. The bent path through 20 is 20 + 15 + 7 = 42, so the global best becomes 42. But node 20 returns only 35 upward, representing 20 -> 15 as the best single downward chain.
At root -10, the left gain is 9 and the right gain is 35. The bent path through the root is 34, which does not beat 42. The root returns 25, but the answer remains the global best 42 from the bend through node 20.
Algorithm
- Initialise a global bestSum to the smallest integer value.
- Define a helper that returns the best downward gain starting at the current node.
- For null, return 0 because an absent child contributes nothing.
- Recursively compute left and right gains, clamping each to at least 0.
- Update bestSum with node.val + leftGain + rightGain for the path bending through this node.
- Return node.val + max(leftGain, rightGain) so the parent receives one extendable chain.
- After DFS finishes, return bestSum.
Solutions
Solution: Postorder gain with global best path
Use this when a tree path may start and end anywhere. It cleanly separates the extendable value returned upward from the complete path scored globally.
Run postorder DFS. Each node receives the best non-negative gains from its children, updates the global answer with the path that bends through itself, and returns only the best single downward chain to its parent.
Step-by-step
- Initialise bestSum to Integer.MIN_VALUE so all-negative trees are handled.
- Return 0 for a null node.
- Recursively compute the left and right child gains.
- Clamp each child gain with max(0, gain).
- Update bestSum with the bent path node.val + leftGain + rightGain.
- Return the extendable downward gain node.val + max(leftGain, rightGain).
O(n)
O(h)
Every node contributes one constant-time combine step; recursion stack depth is the tree height.
Java implementation
Dry Run
Sample input
root = [-10,9,20,null,null,15,7]. Track what each node returns upward versus how it updates the global best.
| node | leftGain | rightGain | returned downward gain | globalBest |
|---|---|---|---|---|
| 9 | 0 | 0 | 9 | 9 |
| 15 | 0 | 0 | 15 | 15 |
| 7 | 0 | 0 | 7 | 15 |
| 20 | 15 | 7 | 35 | 42 |
| -10 | 9 | 35 | 25 | 42 |
Node 20 returns 35 upward, but the answer is 42 because the complete path may bend through 20 and use both children.
Interview Tips
Use the phrase extendable chain for the return value and complete candidate path for the global update. That vocabulary prevents the classic bug of returning both children to the parent. Also mention why bestSum starts at Integer.MIN_VALUE: a tree like [-3] should return -3, not 0.
Likely follow-ups
- How would you return the actual nodes on the maximum-sum path?
- How would the logic change for an N-ary tree where a path can use at most two child branches at a node?
- How would you compute the maximum path sum if every edge also had a weight?
- Can you write an iterative postorder version that preserves the same returned-gain invariant?
Similar Problems
Key Takeaways
- A parent can extend only one downward branch from a child.
- The global best may use both child gains and bend through the current node.
- Negative child gains should be clamped to **0** because they hurt the path.
- Initialise the global best for all-negative inputs, not to **0**.