Binary Tree Maximum Path Sum

Each node reports one branch upward, but tests the full arch against the record

time O(n)space O(h)

A path can bend once, at its highest node, joining a branch going down-left with a branch going down-right into an arch. But an arch cannot be handed up to a parent: extending it would give the path two forks. So each node answers two different questions. It tests the full arch (its value plus both clamped branches) against the global best as a side effect, and it returns only its best single branch (its value plus the larger child branch) so the parent can keep extending a fork-free path. Negative branches are clamped to 0 because including them can only lower a sum.

Details

Animated on: Tree [-10, 9, 20, null, null, 15, 7] — find the largest sum of any path (nodes joined by parent-child edges, no repeats; it need not pass through the root).

Problem:Binary Tree Maximum Path SumHard

Pattern:Tree DFS

Each node reports one branch upward, but tests the full arch against the record

step 1 / 14

-10

best starts at -INFINITY, not 0: a tree of only negative values must still return its least-negative node. Call gain(-10) on the root; the answer will be updated as a side effect while the recursion unwinds.

Pseudocode

1FUNCTION maxPathSum(root):
2  best <- -INFINITY
3  gain(root)
4  RETURN best
5FUNCTION gain(node):
6  IF node = null: RETURN 0
7  left <- MAX(0, gain(node.left))
8  right <- MAX(0, gain(node.right))
9  best <- MAX(best, node.val + left + right)
10  RETURN node.val + MAX(left, right)

← / → step · space play · Home restart

Every step in words

Show all 14 steps

best starts at -INFINITY, not 0: a tree of only negative values must still return its least-negative node. Call gain(-10) on the root; the answer will be updated as a side effect while the recursion unwinds.
gain(-10) cannot decide anything yet — it needs the best downward branch from each child first, so it goes down before it can report up.
gain(9) is a leaf: both null children return 0, so it has no branch to extend. Its arch is just 9 on its own.
Leaf 9: arch = 9, a new best (was -INFINITY), so best <- 9. It returns 9 to its parent — the parent may extend a path down through it, but only one way.
gain(20) cannot decide anything yet — it needs the best downward branch from each child first, so it goes down before it can report up.
gain(15) is a leaf: both null children return 0, so it has no branch to extend. Its arch is just 15 on its own.
Leaf 15: arch = 15, a new best (was 9), so best <- 15. It returns 15 to its parent — the parent may extend a path down through it, but only one way.
gain(7) is a leaf: both null children return 0, so it has no branch to extend. Its arch is just 7 on its own.
Leaf 7: arch = 7, not better than best = 15. It returns 7 to its parent — the parent may extend a path down through it, but only one way.
At 20: left branch = 15, right branch = 7. The arch through this node is 20 + 15 + 7 = 42, a new best (was 15). best <- 42.
20 returns 20 + MAX(15, 7) = 35. It must NOT return the arch 42: a parent extending through 20 can continue into only one of its children, or the path would fork.
At -10: left branch = 9, right branch = 35. The arch through this node is -10 + 9 + 35 = 34, which does not beat best = 42, so best stays.
-10 returns -10 + MAX(9, 35) = 25. It must NOT return the arch 34: a parent extending through -10 can continue into only one of its children, or the path would fork.
Every node has been the top of exactly one arch, so best = 42 is the maximum path sum. The winning path 15 -> 20 -> 7 never passes through the root: this is why the answer is a side effect and not the value gain(root) returns.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Tree Maximum Path Sum in the editor All Binary Trees problems Back to roadmap