Builds on Bottom-Up DFS, which you haven’t finished yet.
Tree DP (Max Path Sum / Diameter)
global_max records the best path that bends at each node.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.
Tree Diameter DP
Postorder ➔ Update Global Summit [L + Node + R] ➔ Return Single Leg [Node + max(L, R)]| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def max_path_sum(root: Optional[TreeNode]) -> int: |
| 10 | """Binary Tree Maximum Path Sum: best path anywhere, bending at most once. |
| 11 | Time: O(N) | Space: O(H) recursion stack |
| 12 | """ |
| 13 | global_max = float('-inf') # -inf, not 0: an all-negative tree still has an answer |
| 14 | |
| 15 | def dfs(node: Optional[TreeNode]) -> int: |
| 16 | nonlocal global_max |
| 17 | if not node: |
| 18 | return 0 # Base case: null node contributes 0 gain |
| 19 | |
| 20 | # 1. Postorder descent; clamp negative returns (decline harmful paths) |
| 21 | left_gain = max(0, dfs(node.left)) |
| 22 | right_gain = max(0, dfs(node.right)) |
| 23 | |
| 24 | # 2. THE SUMMIT BRIDGE: Arched path bending through node + both legs |
| 25 | global_max = max(global_max, node.val + left_gain + right_gain) |
| 26 | |
| 27 | # 3. THE EXTENDABLE LEG: Hand up only ONE best linear branch to parent |
| 28 | return node.val + max(left_gain, right_gain) |
| 29 | |
| 30 | dfs(root) |
| 31 | return global_max |
dfs(node) returns the best downward leg that starts at node, and global_max holds the best path that bends at any node already finished.Every path in a tree has one highest node where it bends, so at each node compute two different things from the children's gains. The summit, node.val + left_gain + right_gain, is the best path bending here and only updates global_max; the leg, node.val + max(left_gain, right_gain), is the only thing returned, because a path continuing up through the parent can use just one side. Clamp gains with max(0, ...) so a negative branch is simply left out.
See it run
Tree DP: the bend and the leg, step by step
left_gain -right_gain -summit -leg -global_max -infanswer not yet
Each circle is a tree node. The bend is the best path that turns at a node, using both children. The leg is one straight path down one side, and it is the only value a node returns to its parent. The list under the tree shows each returned leg.
at nodethe node whose bend and leg are computed nowbest bendthe node where the best path so far turnsleg usedthe edge of a child leg that is added at this nodeleg upthe edge the returned leg travels along, to the parent
Start with global_max = -inf. Each node will compute a bend, which only updates global_max, and a leg, which is the only value it returns.
Gotcha 1 of 5
- The trap
Gotcha 1: Adding a negative leg without
max(0, ...)Mistakeleft_gain = dfs(node.left) right_gain = dfs(node.right)Fixleft_gain = max(0, dfs(node.left)) right_gain = max(0, dfs(node.right))What happens: A path may stop at any node. So a subtree whose best leg is negative should be left out. Without
max(0, ...), that negative leg is added to the summit and to the returned leg. Every path through that node then loses value.Example: root = [2,-1]Mistake: returns 1Fix: returns 2
- The path must start at the root and only go down, as in Maximum Depth of Binary Tree (LC 104), so the root's own return value is the answer and no path bends. See Bottom-Up DFS
Deep Dive
Why each node computes two different numbers
A path in a tree goes down from some node, turns at one highest node, and goes down again on the other side. Every path has exactly one highest node. So the best path in the tree is the best bend over all nodes.
At each node, two questions have two different answers. The first question is: what is the best path that turns at this node? That path can use both children, so its sum is node.val + left_gain + right_gain. Call it the bend. It is only recorded in global_max. The second question is: what can this node offer to its parent? The parent's path continues upward, so it can use only one side of this node. The best offer is node.val + max(left_gain, right_gain). Call it the leg. It is the only value dfs returns.
Take root = [-10, 9, 20, null, null, 15, 7]. Node 9 has a bend of 9 and a leg of 9. Node 15 has a bend of 15 and a leg of 15. Node 7 has a bend of 7 and a leg of 7. Node 20 has left_gain = 15 and right_gain = 7, so its bend is 20 + 15 + 7 = 42 and its leg is 20 + 15 = 35. The root -10 has left_gain = 9 and right_gain = 35, so its bend is 34 and its leg is 25. global_max ends at 42, which is the answer. The root's leg, 25, is not the answer.
Why the returned leg can use only one side
The parent adds the returned value to its own path. A path is a line. It can go down only one side of any node. If a node returned the bend, which uses both sides, the parent would build a path that forks into two branches below the node. That is not a path.
Take root = [1, 2, 3, null, null, 4, 5]. Node 3 has children 4 and 5. Its bend is 3 + 4 + 5 = 12, and 12 is a real path: 4, 3, 5. Its leg is 3 + 5 = 8. The root then has left_gain = 2 and right_gain = 8, so its bend is 1 + 2 + 8 = 11. The answer is 12.
If node 3 returned its bend 12, the root would compute 1 + 2 + 12 = 15. That sum counts 2, 1, 3, 4 and 5. Node 3 would have two neighbours below it (4 and 5) and one above it (1). No single path visits all five nodes, so 15 is wrong.
The two numbers have a simple rule. The bend answers "what is the best path with its turn here?" and goes to global_max. The leg answers "what is the best straight path that starts here and goes down?" and goes to the parent.
Two traps: a negative leg, and returning the wrong thing
A path can stop at any node, so a child with a negative leg should be left out. The code does this with max(0, dfs(node.left)). For root = [2, -1], the child returns -1. Without the clamp, the bend is 2 + (-1) = 1 and the code returns 1. With the clamp, the gain is 0 and the code returns 2.
The start value of global_max must be -inf. A path must contain at least one node. For root = [-3], the only path is the single node -3. With a start of 0, the bend -3 never replaces it, and the code returns 0. That value is not the sum of any path. With -inf, the code returns -3.
The last trap is the line return dfs(root). The root's call returns the root's leg, which covers only paths that go down one side of the root. For root = [1, 2, 3], the root's leg is 1 + 3 = 4, but the best path is 2, 1, 3 with a sum of 6. The code must call dfs(root) for its effect and then return global_max.
The cost, and how it differs from Bottom-Up DFS
Each node is visited once, and each visit does constant work. The time is O(N). The space is O(H) for the recursion stack, where H is the height.
The shape appears in other problems. Diameter of Binary Tree (LC 543) uses the same two numbers with lengths. The leg is the depth of the node. The bend is left_depth + right_depth, the longest path that turns at this node. Longest Univalue Path (LC 687) adds a condition: a child's leg continues through the node only when the child has the same value.
Compare with Bottom-Up DFS. In Maximum Depth of Binary Tree (LC 104), the path must start at the root, so the root's return value is the answer, and no path bends. Here, the best path can lie anywhere, so the answer is stored in global_max. Bottom-Up DFS returns one value that is also the answer. This card returns one value that is only a building block, and the answer is stored on the side.
60-Second Pitch
"Every path has one highest node where it turns, so I compute two numbers at every node. The bend is node.val + left_gain + right_gain. It is the best path that turns here, and I only compare it with global_max. The leg is node.val + max(left_gain, right_gain). It is the only value I return, because my parent can extend only one side. I clamp each child gain with max(0, ...) so a negative branch is left out. I start global_max at -inf, because the path must contain at least one node. I return global_max, not the root's leg. Each node is visited once, so the time is O(N). The space is O(H) for the recursion stack."
Common Questions
- Why do you return the leg and not the bend?
The parent extends the returned value into a longer path. A path can go down only one side of a node. The bend uses both sides, so the parent would get a fork. The leg uses one side, so it is a straight line that the parent can extend.
- Why
max(0, ...)on the child gains? A path may stop at any node. If a child's best leg is negative, the path is better without it. The clamp makes that child add 0. For
[2, -1]the answer is 2 with the clamp and 1 without it.- What are the time and space complexity?
O(N)time, because each node is visited once with constant work. O(H) space for the recursion stack, whereHis the height.global_maxis one number.- How does Diameter of Binary Tree (LC 543) fit this card?
The leg is the depth of the node:
1 + max(left_depth, right_depth). The bend isleft_depth + right_depth, the number of edges of the longest path that turns at this node.global_maxkeeps the largest bend. The answer isglobal_max, not the root's depth.- What changes for Longest Univalue Path (LC 687)?
A child's leg continues through the node only when the child has the same value as the node. Otherwise that side adds 0 to both the bend and the leg. The structure is the same: return the leg, record the bend.
SWE Reasoning
Spot it
- The answer is the best path anywhere in the tree, not only from the root: maximum path sum, diameter, longest path with a condition.
- A path may start and end at any node, and it turns at most once.
- The wording says "any path", "at least one node", "longest" or "may or may not pass through the root".
- A node needs a value to offer its parent that is different from the best answer at the node itself.
- The tree can hold negative values, so a branch may be better left out.
The invariant, step by step
- Every path has one highest node, where it turns. So the answer is the best bend over all nodes.
dfs(node)returns the leg: the best straight path that starts atnodeand goes down one side.- Each child's gain is
max(0, dfs(child)). A negative leg is left out, because a path can stop atnode. - The bend at
nodeisnode.val + left_gain + right_gain. It is compared withglobal_maxand never returned. - The leg is
node.val + max(left_gain, right_gain). It is returned, because the parent's path can use only one side ofnode. - When the recursion ends,
global_maxis the best bend over all nodes. That is the best path.
Traps
- Returning the bend. The parent would build a path that forks. Return the leg.
- Returning
dfs(root). It is the root's leg, not the best path. Returnglobal_max. - No
max(0, ...)on the gains. A negative leg lowers every path through the node. global_max = 0at the start. If all values are negative, the answer must be the largest single value. Use-inf.- Forgetting the condition in problems like Longest Univalue Path (LC 687). A leg may continue through a node only when the values match.
Practice
Builds on Bottom-Up DFS, which you haven’t finished yet.
Tree DP (Max Path Sum / Diameter)
global_max records the best path that bends at each node.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.
Tree Diameter DP
Postorder ➔ Update Global Summit [L + Node + R] ➔ Return Single Leg [Node + max(L, R)]| 1 | from typing import Optional |
| 2 | |
| 3 | class TreeNode: |
| 4 | def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): |
| 5 | self.val = val |
| 6 | self.left = left |
| 7 | self.right = right |
| 8 | |
| 9 | def max_path_sum(root: Optional[TreeNode]) -> int: |
| 10 | """Binary Tree Maximum Path Sum: best path anywhere, bending at most once. |
| 11 | Time: O(N) | Space: O(H) recursion stack |
| 12 | """ |
| 13 | global_max = float('-inf') # -inf, not 0: an all-negative tree still has an answer |
| 14 | |
| 15 | def dfs(node: Optional[TreeNode]) -> int: |
| 16 | nonlocal global_max |
| 17 | if not node: |
| 18 | return 0 # Base case: null node contributes 0 gain |
| 19 | |
| 20 | # 1. Postorder descent; clamp negative returns (decline harmful paths) |
| 21 | left_gain = max(0, dfs(node.left)) |
| 22 | right_gain = max(0, dfs(node.right)) |
| 23 | |
| 24 | # 2. THE SUMMIT BRIDGE: Arched path bending through node + both legs |
| 25 | global_max = max(global_max, node.val + left_gain + right_gain) |
| 26 | |
| 27 | # 3. THE EXTENDABLE LEG: Hand up only ONE best linear branch to parent |
| 28 | return node.val + max(left_gain, right_gain) |
| 29 | |
| 30 | dfs(root) |
| 31 | return global_max |
dfs(node) returns the best downward leg that starts at node, and global_max holds the best path that bends at any node already finished.Every path in a tree has one highest node where it bends, so at each node compute two different things from the children's gains. The summit, node.val + left_gain + right_gain, is the best path bending here and only updates global_max; the leg, node.val + max(left_gain, right_gain), is the only thing returned, because a path continuing up through the parent can use just one side. Clamp gains with max(0, ...) so a negative branch is simply left out.
See it run
Tree DP: the bend and the leg, step by step
left_gain -right_gain -summit -leg -global_max -infanswer not yet
Each circle is a tree node. The bend is the best path that turns at a node, using both children. The leg is one straight path down one side, and it is the only value a node returns to its parent. The list under the tree shows each returned leg.
at nodethe node whose bend and leg are computed nowbest bendthe node where the best path so far turnsleg usedthe edge of a child leg that is added at this nodeleg upthe edge the returned leg travels along, to the parent
Start with global_max = -inf. Each node will compute a bend, which only updates global_max, and a leg, which is the only value it returns.
Gotcha 1 of 5
- The trap
Gotcha 1: Adding a negative leg without
max(0, ...)Mistakeleft_gain = dfs(node.left) right_gain = dfs(node.right)Fixleft_gain = max(0, dfs(node.left)) right_gain = max(0, dfs(node.right))What happens: A path may stop at any node. So a subtree whose best leg is negative should be left out. Without
max(0, ...), that negative leg is added to the summit and to the returned leg. Every path through that node then loses value.Example: root = [2,-1]Mistake: returns 1Fix: returns 2
- The path must start at the root and only go down, as in Maximum Depth of Binary Tree (LC 104), so the root's own return value is the answer and no path bends. See Bottom-Up DFS
Deep Dive
Why each node computes two different numbers
A path in a tree goes down from some node, turns at one highest node, and goes down again on the other side. Every path has exactly one highest node. So the best path in the tree is the best bend over all nodes.
At each node, two questions have two different answers. The first question is: what is the best path that turns at this node? That path can use both children, so its sum is node.val + left_gain + right_gain. Call it the bend. It is only recorded in global_max. The second question is: what can this node offer to its parent? The parent's path continues upward, so it can use only one side of this node. The best offer is node.val + max(left_gain, right_gain). Call it the leg. It is the only value dfs returns.
Take root = [-10, 9, 20, null, null, 15, 7]. Node 9 has a bend of 9 and a leg of 9. Node 15 has a bend of 15 and a leg of 15. Node 7 has a bend of 7 and a leg of 7. Node 20 has left_gain = 15 and right_gain = 7, so its bend is 20 + 15 + 7 = 42 and its leg is 20 + 15 = 35. The root -10 has left_gain = 9 and right_gain = 35, so its bend is 34 and its leg is 25. global_max ends at 42, which is the answer. The root's leg, 25, is not the answer.
Why the returned leg can use only one side
The parent adds the returned value to its own path. A path is a line. It can go down only one side of any node. If a node returned the bend, which uses both sides, the parent would build a path that forks into two branches below the node. That is not a path.
Take root = [1, 2, 3, null, null, 4, 5]. Node 3 has children 4 and 5. Its bend is 3 + 4 + 5 = 12, and 12 is a real path: 4, 3, 5. Its leg is 3 + 5 = 8. The root then has left_gain = 2 and right_gain = 8, so its bend is 1 + 2 + 8 = 11. The answer is 12.
If node 3 returned its bend 12, the root would compute 1 + 2 + 12 = 15. That sum counts 2, 1, 3, 4 and 5. Node 3 would have two neighbours below it (4 and 5) and one above it (1). No single path visits all five nodes, so 15 is wrong.
The two numbers have a simple rule. The bend answers "what is the best path with its turn here?" and goes to global_max. The leg answers "what is the best straight path that starts here and goes down?" and goes to the parent.
Two traps: a negative leg, and returning the wrong thing
A path can stop at any node, so a child with a negative leg should be left out. The code does this with max(0, dfs(node.left)). For root = [2, -1], the child returns -1. Without the clamp, the bend is 2 + (-1) = 1 and the code returns 1. With the clamp, the gain is 0 and the code returns 2.
The start value of global_max must be -inf. A path must contain at least one node. For root = [-3], the only path is the single node -3. With a start of 0, the bend -3 never replaces it, and the code returns 0. That value is not the sum of any path. With -inf, the code returns -3.
The last trap is the line return dfs(root). The root's call returns the root's leg, which covers only paths that go down one side of the root. For root = [1, 2, 3], the root's leg is 1 + 3 = 4, but the best path is 2, 1, 3 with a sum of 6. The code must call dfs(root) for its effect and then return global_max.
The cost, and how it differs from Bottom-Up DFS
Each node is visited once, and each visit does constant work. The time is O(N). The space is O(H) for the recursion stack, where H is the height.
The shape appears in other problems. Diameter of Binary Tree (LC 543) uses the same two numbers with lengths. The leg is the depth of the node. The bend is left_depth + right_depth, the longest path that turns at this node. Longest Univalue Path (LC 687) adds a condition: a child's leg continues through the node only when the child has the same value.
Compare with Bottom-Up DFS. In Maximum Depth of Binary Tree (LC 104), the path must start at the root, so the root's return value is the answer, and no path bends. Here, the best path can lie anywhere, so the answer is stored in global_max. Bottom-Up DFS returns one value that is also the answer. This card returns one value that is only a building block, and the answer is stored on the side.
60-Second Pitch
"Every path has one highest node where it turns, so I compute two numbers at every node. The bend is node.val + left_gain + right_gain. It is the best path that turns here, and I only compare it with global_max. The leg is node.val + max(left_gain, right_gain). It is the only value I return, because my parent can extend only one side. I clamp each child gain with max(0, ...) so a negative branch is left out. I start global_max at -inf, because the path must contain at least one node. I return global_max, not the root's leg. Each node is visited once, so the time is O(N). The space is O(H) for the recursion stack."
Common Questions
- Why do you return the leg and not the bend?
The parent extends the returned value into a longer path. A path can go down only one side of a node. The bend uses both sides, so the parent would get a fork. The leg uses one side, so it is a straight line that the parent can extend.
- Why
max(0, ...)on the child gains? A path may stop at any node. If a child's best leg is negative, the path is better without it. The clamp makes that child add 0. For
[2, -1]the answer is 2 with the clamp and 1 without it.- What are the time and space complexity?
O(N)time, because each node is visited once with constant work. O(H) space for the recursion stack, whereHis the height.global_maxis one number.- How does Diameter of Binary Tree (LC 543) fit this card?
The leg is the depth of the node:
1 + max(left_depth, right_depth). The bend isleft_depth + right_depth, the number of edges of the longest path that turns at this node.global_maxkeeps the largest bend. The answer isglobal_max, not the root's depth.- What changes for Longest Univalue Path (LC 687)?
A child's leg continues through the node only when the child has the same value as the node. Otherwise that side adds 0 to both the bend and the leg. The structure is the same: return the leg, record the bend.
SWE Reasoning
Spot it
- The answer is the best path anywhere in the tree, not only from the root: maximum path sum, diameter, longest path with a condition.
- A path may start and end at any node, and it turns at most once.
- The wording says "any path", "at least one node", "longest" or "may or may not pass through the root".
- A node needs a value to offer its parent that is different from the best answer at the node itself.
- The tree can hold negative values, so a branch may be better left out.
The invariant, step by step
- Every path has one highest node, where it turns. So the answer is the best bend over all nodes.
dfs(node)returns the leg: the best straight path that starts atnodeand goes down one side.- Each child's gain is
max(0, dfs(child)). A negative leg is left out, because a path can stop atnode. - The bend at
nodeisnode.val + left_gain + right_gain. It is compared withglobal_maxand never returned. - The leg is
node.val + max(left_gain, right_gain). It is returned, because the parent's path can use only one side ofnode. - When the recursion ends,
global_maxis the best bend over all nodes. That is the best path.
Traps
- Returning the bend. The parent would build a path that forks. Return the leg.
- Returning
dfs(root). It is the root's leg, not the best path. Returnglobal_max. - No
max(0, ...)on the gains. A negative leg lowers every path through the node. global_max = 0at the start. If all values are negative, the answer must be the largest single value. Use-inf.- Forgetting the condition in problems like Longest Univalue Path (LC 687). A leg may continue through a node only when the values match.