Pattern visualizer

Binary Tree Maximum Path Sum

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. 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)..

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

time O(n)space O(h)step 1 / 14

-10

line 2

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap