The problem
A path is any chain of connected nodes (each used at most once); it doesn’t need to pass through the root. Find the largest possible sum of values along a path.
Input: [−10, 9, 20, null, null, 15, 7] Output: 42 (15 → 20 → 7)
Picture it
Picture a tree of coins, where negative values are debts. Each node reports to its parent the best one-way trail going down from it (and ignores a side that would lose money, i.e. treats it as 0). At each node we also try the bent trail left + me + right as a candidate answer.
How to recognise it
- A path may start and end anywhere and bend once at its highest node, so it need not touch the root or a leaf.
- Values can be negative, so a longer path is not always better: sometimes a branch should be left out.
- Like the diameter problem, each node needs one number from each child (the best straight path going down), and a bent path is completed at its top node.
- Up to 3 × 10^4 nodes, so do O(1) work per node.
Start with brute force
Every path has a highest node where it bends. For each node, compute the best downward path from each child with a separate helper, keep only positive ones, and add the node's value.
def down(node): # best path starting here, going down
if not node:
return 0
return node.val + max(0, down(node.left), down(node.right))
def max_path_brute(root):
best = -inf
def visit(node):
nonlocal best
if not node:
return
bend = node.val + max(0, down(node.left)) + max(0, down(node.right))
best = max(best, bend)
visit(node.left)
visit(node.right)
visit(root)
return best
Each down call walks a whole subtree, once for every ancestor: O(n log n) on a balanced tree, O(n²) on a chain, about 4.5 × 10^8 steps for 3 × 10^4 nodes. Too slow.
From brute force to the idea
- Find the waste.
down(child)is recomputed at every ancestor, although it never changes. - Compute it once, bottom-up.
gain(node)returns the best downward path starting atnode. The parent receives it as a return value. - Drop losing branches.
max(gain(child), 0)means "use this branch only if it adds something". A child path with a negative sum is replaced by 0, that is, not taken. - Record the bend. With
landrin hand,node.val + l + ris the best path whose highest node is this one. Keep the best inbest. - Return a straight path. The parent can extend only one branch, so return
node.val + max(l, r).
This is the key idea: one DFS returns the best straight path down, while each node also records the best path that bends at it.
best must start at -inf (from math import inf, which the page leaves out), because the answer can be negative.
The key idea
DFS returns the best downward gain; update best with left + node + right, clamping negative gains to 0. O(n).
Python solution
def max_path_sum(root):
best = -inf
def gain(node):
nonlocal best
if not node:
return 0
l = max(gain(node.left), 0) # ignore losing branches
r = max(gain(node.right), 0)
best = max(best, node.val + l + r)
return node.val + max(l, r)
gain(root)
return bestLeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n log n) balanced, O(n²) chain: each downward gain recomputed per ancestor | O(h): recursion only, h is the height |
| One DFS (shown code) | O(n): each node visited once, O(1) work | O(h): one stack frame per level, h = n for a chain |
Edge cases
- Single negative node (
[-3]): returns −3; a path needs at least one node. - All negative (
[-2, -1]): returns −1, the largest single value. - Negative child (
[2, -1]): returns 2; the −1 branch is dropped. - Best path avoids the root (
[-10, 9, 20, null, null, 15, 7]): returns 42 (15 → 20 → 7). - Very deep tree: a chain of about 1,000 nodes exceeds Python's default recursion limit (
RecursionError), and LeetCode allows 3 × 10^4 nodes. Use an explicit stack (post-order) if needed.
Common mistakes
- Starting
bestat 0, which returns 0 for an all-negative tree, although no empty path is allowed. - Returning
node.val + l + rto the parent: a path that already bends cannot be extended. - Clamping the node's own value at 0. Only the child gains are optional; the node itself is always on the path.
- Forgetting
nonlocal best.
Return the largest sum of a path that only goes downwards: from some node to one of its descendants (or a single node), with no bend. For [-10, 9, 20, null, null, 15, 7] the answer is 35 (20 → 15). Describe your approach, then write it if you like.
Compare with our answer
Same bottom-up gain, but there is no bend to record: the best path starting at each node is itself a candidate.
from math import inf
def max_down_path(root):
best = -inf
def gain(node):
nonlocal best
if not node:
return 0
g = node.val + max(gain(node.left), gain(node.right), 0)
best = max(best, g)
return g
gain(root)
return best
Time O(n), space O(h).
A strong answer mentions: that the candidate at each node is the returned straight path, clamping child gains at 0, and starting best at minus infinity.
1. A tree of rooms has a score per room (some negative). You must choose a connected route through rooms, each used once, with the best total. Which approach fits best?
A route is a path that bends at one top node, exactly as here, so one DFS in O(n) records every bend. Root-only sums miss routes elsewhere, and positive rooms may not be connected.
2. Why does gain return node.val + max(l, r) but record node.val + l + r?
A path through the parent continues down one side only, so gain reports the best straight branch. The bent path l + r through this node is complete and is only compared with best.
3. A learner starts with best = 0 instead of -inf. Which tree now gets a wrong answer?
Every bend at a single −3 node gives −3, which never beats 0, so the function returns 0. When any path has a sum of at least 0, the start value is beaten anyway, as in the other trees.
Score 60% or more and the lesson is marked complete.