Binary Tree Maximum Path Sum (LeetCode 124)
Think of a path here as any walk through the tree that only ever moves along real edges, never revisiting a node, and never required to touch the root.
Add up the values of every node along a path and you get that path's sum. Given the root of a binary tree, find the largest such sum over any non-empty path you could trace.
Worked Examples
root = [1,2,3]6root = [-10,9,20,null,null,15,7]42⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 3 * 104].-1000 <= Node.val <= 1000
Core Insight
A path can only turn at one highest node. A parent can only receive a single branch, so clamp negative branches to 0 and return node.val + max(L, R) upward while updating global ans with node.val + L + R.
Real-World Scenario & Production Applications
Network routing path capacity optimization, VLSI hierarchical circuit delay analysis.
Subproblems & Recurrence Decomposition3 Phases
A parent can only extend ONE of its child's paths through itself -- never both -- so each node returns the better of its two downward branches plus its own value, clamping negative branches to 0 since including them would only hurt.
left_gain = max(dfs(node.left), 0)
right_gain = max(dfs(node.right), 0)
return node.val + max(left_gain, right_gain)Step-by-Step Execution Trace Table
| Step | Call Frame | Action | Left Gain (max(0, L)) | Right Gain (max(0, R)) | Local Summit (val + L + R) | Global Max Best | Return to Parent (val + max(L, R)) |
|---|---|---|---|---|---|---|---|
| 1 | Node 9 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 9 + 0 + 0 = 9 | 9 | 9 + max(0,0) = 9 |
| 2 | Node 15 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 15 + 0 + 0 = 15 | 15 | 15 + max(0,0) = 15 |
| 3 | Node 7 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 7 + 0 + 0 = 7 | 15 | 7 + max(0,0) = 7 |
| 4 | Node 20 | ⬆️ COMBINE | 15 (from 15) | 7 (from 7) | 20 + 15 + 7 = 42 | 42 | 20 + max(15,7) = 35 |
| 5 | Node -10 (root) | ⬆️ SUMMIT | 9 (from 9) | 35 (from 20) | -10 + 9 + 35 = 34 | 42 | -10 + max(9,35) = 25 |
root = [1,2,3]6| Step | Call Frame | Action | Left Gain (max(0, L)) | Right Gain (max(0, R)) | Local Summit (val + L + R) | Global Max Best | Return to Parent (val + max(L, R)) |
|---|---|---|---|---|---|---|---|
| 1 | Node 9 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 9 + 0 + 0 = 9 | 9 | 9 + max(0,0) = 9 |
| 2 | Node 15 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 15 + 0 + 0 = 15 | 15 | 15 + max(0,0) = 15 |
| 3 | Node 7 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 7 + 0 + 0 = 7 | 15 | 7 + max(0,0) = 7 |
| 4 | Node 20 | ⬆️ COMBINE | 15 (from 15) | 7 (from 7) | 20 + 15 + 7 = 42 | 42 | 20 + max(15,7) = 35 |
| 5 | Node -10 (root) | ⬆️ SUMMIT | 9 (from 9) | 35 (from 20) | -10 + 9 + 35 = 34 | 42 | -10 + max(9,35) = 25 |
| 1 | left_gain = max(0, dfs(node.left)) |
| 2 | right_gain = max(0, dfs(node.right)) |
| 3 | global_max = max(global_max, node.val + left_gain + right_gain) |
| 4 | return node.val + max(left_gain, right_gain) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every possible path sums differently depending on whether it bends through a node or continues straight through it — and this is the one archetype where "the answer at this node" and "what I report to my parent" are genuinely two different numbers.
🏔️ The Analogy: The Summit of a Path vs. the Trail You Can Still Extend
Every possible path through the tree has exactly one highest point — call it its "summit." At that summit, the path can bend, using both the left leg and the right leg. But if you're a lower node reporting your best result up to your parent, your parent can only extend a path through you in one direction — they can't accept a path that already bent at you and also expect to extend it further, because a path can't fork twice. So at every node, you calculate two separate things: the best "summit" score achievable if the path bends right here (using both legs), which you compare against the global best-so-far — and the best "single leg" score to actually hand up to your parent, since that's all a parent can legally use.
🔑 The Key Idea in the Code
global_max and the function's return value answer two different questions, computed from the exact same two recursive calls — that's the entire trick. max(..., 0) handles negative subtrees by simply declining to use them, since a path is always allowed to stop early.
Two-child forking return bug: Returning the summit path (
node.val + left_gain + right_gain) to the parent caller. A valid path cannot fork twice; the return value upward must be strictly linear:node.val + max(left_gain, right_gain).Negative subtree bleed: Failing to clamp negative child subtree gains with
max(0, gain). If a child branch yields a negative sum, including it decreases the path total; declining to extend into that child (taking 0) is always optimal.Zero initialization on all-negative trees: Initializing
global_max = 0. If the tree contains only negative numbers (e.g.root = [-3]), initializing to 0 outputs 0 instead of the maximum single node value-3. Must initialize to-float('inf')orroot.val.Stack overflow on skewed chains: CPython limit is 1000 frames. Deep trees with
O(N)height require iterative stack traversal or increasing recursion limit.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Maximum path sum in binary tree between any two nodes, non-empty path, nodes may have negative values.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
At each node: left_gain = max(0, dfs(node.left)) and right_gain = max(0, dfs(node.right)); the summit node.val + left_gain + right_gain updates global_max, and dfs returns the leg node.val + max(left_gain, right_gain).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Clamp the children's gains, never
node.valitself: a path holds at least one node, so on[-3]the summit is-3 + 0 + 0, not 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Tree Diameter DP. Every path in a tree has one highest node where it bends, so at each node I look at two things built from the children's gains. The summit, the node's value plus the best left gain and the best right gain, is the best path that bends right here, and I only use it to update global_max. The leg, the node's value plus the larger of the two gains, is what I return, because a path that continues up through the parent can only use one side. I clamp each gain at zero, so a negative subtree is simply left out. The trap is returning the summit instead of the leg: the parent would then build a path that forks. I start global_max at minus infinity, since an all-negative tree still has an answer. Each node is visited once, so it's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at the postorder DFS traversal: Every node in the binary tree is visited exactly once. For each node, we recursively compute left and right subtree gains in O(1) per return, clamp negative branches to 0 (left_gain = max(0, dfs(node.left))), update global_max = max(global_max, node.val + left_gain + right_gain), and return node.val + max(left_gain, right_gain) upward. With O(1) work performed per node, total time is strictly O(N).
O(H) recursion stack
Look at memory allocations: We allocate zero dynamic arrays or hash tables. The recursion call stack depth equals the height of the tree H. For a balanced tree, H = O(log N); in the worst-case degenerate linear tree (linked list structure), H = O(N). Auxiliary space is strictly O(H).
Derivation Progression
Compute downward gain from children before evaluating current turning path.
Combines both branches into a full U-turn path candidate in O(1) time.
Every node evaluated exactly once in bottom-up traversal.
Variable Definitions
Total number of nodes in the binary tree
Height of the binary tree (log N balanced, N degenerate)
Memory Architecture & Bounds
O(H) Recursion frames equal to tree height (O(log N) balanced, O(N) worst)
O(1) Only the scalar global_max
O(1) Returns scalar maximum path sum
Boundary Best / Worst Cases
visit all nodes.
.
visit all nodes.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum path sum", "path connecting any two nodes". The best path may bend at any node, not only the root: Tree Diameter DP.
, node values . Time budget is strictly linear time.
A chain of nodes is calls deep, past CPython's default recursion limit of 1000: raise the limit or run the same postorder with an explicit stack.
Binary Tree Maximum Path Sum (LeetCode 124)
Think of a path here as any walk through the tree that only ever moves along real edges, never revisiting a node, and never required to touch the root.
Add up the values of every node along a path and you get that path's sum. Given the root of a binary tree, find the largest such sum over any non-empty path you could trace.
Worked Examples
root = [1,2,3]6root = [-10,9,20,null,null,15,7]42⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range [1, 3 * 104].-1000 <= Node.val <= 1000
Core Insight
A path can only turn at one highest node. A parent can only receive a single branch, so clamp negative branches to 0 and return node.val + max(L, R) upward while updating global ans with node.val + L + R.
Real-World Scenario & Production Applications
Network routing path capacity optimization, VLSI hierarchical circuit delay analysis.
Subproblems & Recurrence Decomposition3 Phases
A parent can only extend ONE of its child's paths through itself -- never both -- so each node returns the better of its two downward branches plus its own value, clamping negative branches to 0 since including them would only hurt.
left_gain = max(dfs(node.left), 0)
right_gain = max(dfs(node.right), 0)
return node.val + max(left_gain, right_gain)Step-by-Step Execution Trace Table
| Step | Call Frame | Action | Left Gain (max(0, L)) | Right Gain (max(0, R)) | Local Summit (val + L + R) | Global Max Best | Return to Parent (val + max(L, R)) |
|---|---|---|---|---|---|---|---|
| 1 | Node 9 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 9 + 0 + 0 = 9 | 9 | 9 + max(0,0) = 9 |
| 2 | Node 15 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 15 + 0 + 0 = 15 | 15 | 15 + max(0,0) = 15 |
| 3 | Node 7 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 7 + 0 + 0 = 7 | 15 | 7 + max(0,0) = 7 |
| 4 | Node 20 | ⬆️ COMBINE | 15 (from 15) | 7 (from 7) | 20 + 15 + 7 = 42 | 42 | 20 + max(15,7) = 35 |
| 5 | Node -10 (root) | ⬆️ SUMMIT | 9 (from 9) | 35 (from 20) | -10 + 9 + 35 = 34 | 42 | -10 + max(9,35) = 25 |
root = [1,2,3]6| Step | Call Frame | Action | Left Gain (max(0, L)) | Right Gain (max(0, R)) | Local Summit (val + L + R) | Global Max Best | Return to Parent (val + max(L, R)) |
|---|---|---|---|---|---|---|---|
| 1 | Node 9 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 9 + 0 + 0 = 9 | 9 | 9 + max(0,0) = 9 |
| 2 | Node 15 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 15 + 0 + 0 = 15 | 15 | 15 + max(0,0) = 15 |
| 3 | Node 7 (leaf) | ⬆️ EVAL | 0 (None) | 0 (None) | 7 + 0 + 0 = 7 | 15 | 7 + max(0,0) = 7 |
| 4 | Node 20 | ⬆️ COMBINE | 15 (from 15) | 7 (from 7) | 20 + 15 + 7 = 42 | 42 | 20 + max(15,7) = 35 |
| 5 | Node -10 (root) | ⬆️ SUMMIT | 9 (from 9) | 35 (from 20) | -10 + 9 + 35 = 34 | 42 | -10 + max(9,35) = 25 |
| 1 | left_gain = max(0, dfs(node.left)) |
| 2 | right_gain = max(0, dfs(node.right)) |
| 3 | global_max = max(global_max, node.val + left_gain + right_gain) |
| 4 | return node.val + max(left_gain, right_gain) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every possible path sums differently depending on whether it bends through a node or continues straight through it — and this is the one archetype where "the answer at this node" and "what I report to my parent" are genuinely two different numbers.
🏔️ The Analogy: The Summit of a Path vs. the Trail You Can Still Extend
Every possible path through the tree has exactly one highest point — call it its "summit." At that summit, the path can bend, using both the left leg and the right leg. But if you're a lower node reporting your best result up to your parent, your parent can only extend a path through you in one direction — they can't accept a path that already bent at you and also expect to extend it further, because a path can't fork twice. So at every node, you calculate two separate things: the best "summit" score achievable if the path bends right here (using both legs), which you compare against the global best-so-far — and the best "single leg" score to actually hand up to your parent, since that's all a parent can legally use.
🔑 The Key Idea in the Code
global_max and the function's return value answer two different questions, computed from the exact same two recursive calls — that's the entire trick. max(..., 0) handles negative subtrees by simply declining to use them, since a path is always allowed to stop early.
Two-child forking return bug: Returning the summit path (
node.val + left_gain + right_gain) to the parent caller. A valid path cannot fork twice; the return value upward must be strictly linear:node.val + max(left_gain, right_gain).Negative subtree bleed: Failing to clamp negative child subtree gains with
max(0, gain). If a child branch yields a negative sum, including it decreases the path total; declining to extend into that child (taking 0) is always optimal.Zero initialization on all-negative trees: Initializing
global_max = 0. If the tree contains only negative numbers (e.g.root = [-3]), initializing to 0 outputs 0 instead of the maximum single node value-3. Must initialize to-float('inf')orroot.val.Stack overflow on skewed chains: CPython limit is 1000 frames. Deep trees with
O(N)height require iterative stack traversal or increasing recursion limit.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Maximum path sum in binary tree between any two nodes, non-empty path, nodes may have negative values.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
At each node: left_gain = max(0, dfs(node.left)) and right_gain = max(0, dfs(node.right)); the summit node.val + left_gain + right_gain updates global_max, and dfs returns the leg node.val + max(left_gain, right_gain).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Clamp the children's gains, never
node.valitself: a path holds at least one node, so on[-3]the summit is-3 + 0 + 0, not 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Tree Diameter DP. Every path in a tree has one highest node where it bends, so at each node I look at two things built from the children's gains. The summit, the node's value plus the best left gain and the best right gain, is the best path that bends right here, and I only use it to update global_max. The leg, the node's value plus the larger of the two gains, is what I return, because a path that continues up through the parent can only use one side. I clamp each gain at zero, so a negative subtree is simply left out. The trap is returning the summit instead of the leg: the parent would then build a path that forks. I start global_max at minus infinity, since an all-negative tree still has an answer. Each node is visited once, so it's
O(N)time and O(H) recursion stack.
Complexity & Mathematical Proof
O(N)
Look at the postorder DFS traversal: Every node in the binary tree is visited exactly once. For each node, we recursively compute left and right subtree gains in O(1) per return, clamp negative branches to 0 (left_gain = max(0, dfs(node.left))), update global_max = max(global_max, node.val + left_gain + right_gain), and return node.val + max(left_gain, right_gain) upward. With O(1) work performed per node, total time is strictly O(N).
O(H) recursion stack
Look at memory allocations: We allocate zero dynamic arrays or hash tables. The recursion call stack depth equals the height of the tree H. For a balanced tree, H = O(log N); in the worst-case degenerate linear tree (linked list structure), H = O(N). Auxiliary space is strictly O(H).
Derivation Progression
Compute downward gain from children before evaluating current turning path.
Combines both branches into a full U-turn path candidate in O(1) time.
Every node evaluated exactly once in bottom-up traversal.
Variable Definitions
Total number of nodes in the binary tree
Height of the binary tree (log N balanced, N degenerate)
Memory Architecture & Bounds
O(H) Recursion frames equal to tree height (O(log N) balanced, O(N) worst)
O(1) Only the scalar global_max
O(1) Returns scalar maximum path sum
Boundary Best / Worst Cases
visit all nodes.
.
visit all nodes.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum path sum", "path connecting any two nodes". The best path may bend at any node, not only the root: Tree Diameter DP.
, node values . Time budget is strictly linear time.
A chain of nodes is calls deep, past CPython's default recursion limit of 1000: raise the limit or run the same postorder with an explicit stack.