Trees · LC #124
Binary Tree Maximum Path Sum
Find the maximum sum path in a binary tree where a path can start and end at any node. Post-order DFS computes the best single-branch gain from each node upward while updating a global max with the best through-path at each node.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge between them. A node can only appear in the sequence at most once. The path does not need to pass through the root. Given the root of a binary tree, return the maximum path sum of any non-empty path.
Sample I/O
Input: [-10,9,20,null,null,15,7] Output: 42 (path: 15→20→7) Input: [-3] Output: -3
Time: O(n) · Space: O(h)
Intuition
How to Think About It
Intuition
Post-order DFS works because the maximum path through a node = node.val + best_from_left + best_from_right. But we can only return one branch upward (a path can't fork). So: update global max with the through-path, but return the single best branch to parent. Clamping gains at 0 elegantly handles negative subtrees.
Core Concept
DFS returns the max "single-branch gain" from a node upward: `node.val + max(0, left_gain, right_gain)` (take better branch or skip with 0 if negative). Update global `maxSum = max(maxSum, node.val + max(0, left_gain) + max(0, right_gain))` at each node. Return the single-branch value to parent.
When to use
Any "max/min path through a binary tree" problem. Also used as a template for diameter, longest path with constraints, and path sum variants.
When NOT to use
When the path must start/end at root or a leaf - adds constraints that require different bookkeeping.
Key Insights
What to Know Cold
- Key distinction: global update uses BOTH branches; return to parent uses ONLY ONE branch (path can't fork going up).
- Clamp gains at 0: `max(0, gain)` - discard negative subtrees rather than being dragged down.
- Global max must be initialized to -Infinity (not 0) to handle all-negative trees.
- A single node is a valid path - covered by the base case returning 0 for nulls.
- The "return vs update" duality is the core insight of this problem.
2 examples
Worked Examples
Path through internal node
[-10,9,20,null,null,15,7] - max path is 15+20+7=42.
dfs(15)=15, dfs(7)=7. At node 20: maxSum = max(-∞, 20+15+7)=42. Return 20+max(15,7)=35. At -10: maxSum = max(42, -10+max(9,0)+35)=42. Final: 42.
function maxPathSum(root: TreeNode | null): number {
let maxSum = -Infinity;
function dfs(node: TreeNode|null): number {
if (!node) return 0;
const left = Math.max(0, dfs(node.left));
const right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right);
return node.val + Math.max(left, right);
}
dfs(root);
return maxSum;
}Output: 42
Shows the "update with both branches, return one branch" duality clearly.
All-negative tree
Single node [-3] - must take the only path.
dfs(-3): left=max(0,0)=0, right=0. maxSum=max(-∞,-3+0+0)=-3. Return -3+0=-3.
Output: -3
Validates -Infinity initialization and 0-clamp for negative nodes.