Max Path Sum
At each node, compute the best path passing through it: node value + max(0, left gain) + max(0, right gain). Update the global max. Return to the parent: node value + max(0, best single child gain) — because a path can't branch.
How It Works
Max path sum asks for the highest-sum path between any two nodes, where the path may bend through a node connecting its left and right subtrees. The bottom-up trick is to compute two different quantities at each node. The first is the best arch through the node — node value plus max(0, left gain) plus max(0, right gain) — which updates a global maximum. The second is what the node returns to its parent: node value plus the better single child gain, clamped at zero, because a path continuing upward cannot branch into both subtrees.
Clamping negative child gains to zero elegantly handles negative values: a subtree that hurts the total is simply excluded. One post-order pass touches each node once, giving O(n) time and O(h) recursion space — far better than enumerating all O(n^2) node pairs and their connecting paths.
Step-by-Step Visualization
Code
static int maxSum;
static int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
dfs(root);
return maxSum;
}
static int dfs(TreeNode node) {
if (node == null) return 0;
int left = Math.max(0, dfs(node.left));
int right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left, right);
}
// Tree: [-10, 9, 20, null, null, 15, 7] → max path = 42 (15→20→7)Tips & Gotchas
Practice Problems
- 1Binary Tree Maximum Path Sum
- 2Path Sum III
- 3Longest Univalue Path
- 4Diameter of Binary Tree
About the Path Problems Pattern
Find paths in a tree that optimize some value (max sum, min length, specific target). Paths can go root-to-leaf, or through any nodes. The key insight: at each node, the best path either goes through it or doesn't.
Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.
Common Trees Interview Problems
- Maximum Depth of Binary Tree
- Validate BST
- Binary Tree Level Order Traversal
- Lowest Common Ancestor
- Serialize and Deserialize Binary Tree
- Diameter of Binary Tree
Frequently Asked Questions
Why can a node use both children for the global answer but only one for its return value?
A path that goes up to the parent enters the node from above and can extend into at most one subtree; using both would create a fork, which is not a simple path. The through-the-node arch is only valid as a complete path, so it feeds the global max but never propagates upward.
How are all-negative trees handled correctly?
Initialize the global maximum to negative infinity, not zero, and always include the node's own value in the through-path computation. The max(0, gain) clamps only apply to child contributions, so the best single node is still found when every value is negative.
How does this pattern differ from root-to-leaf path sum problems?
Root-to-leaf problems fix both endpoints, so a simple top-down accumulation works. Max path sum allows arbitrary endpoints, so you need the bottom-up two-quantity approach: a local answer that may bend through each node plus a straight-line gain returned to the parent.