Binary Tree Maximum Path Sum

Hard#124tree nodes

You get the root of a binary tree whose values can be negative. A path goes from node to node along the edges, visits each node at most once and has at least one node; it does not have to pass through the root. Find the largest sum of values on a path. Our tree: -5 with children 3 and 6; 3 has children 7 and 9; 9 has a left child -4; 6 has a right child -1. The answer is 19: the path 7 → 3 → 9.

124 Binary Tree Maximum Path SumWalkthrough · 1×

Example: find the path with the largest sum in a tree with negative values: each call returns the best branch down from its node and updates the best path that bends at it.

best = -∞nonenonenonenonenonenonenonenone-53679-1-4call stacktop on the right—
not visitedwaiting on the call stackcurrent callthe path weighed now, or the best so farreturned, ↑ its best branch downa negative branch, dropped

best = -∞: values can be negative, so the first path has to win whatever its sum

01/61
restart · back · play · step
Speed
1function maxPathSum(root):
2 best = -infinity // shared by every call of gain
3 gain(root)
4 return best
5
6function gain(node):
7 if node is none:
8 return 0
9 left = max(gain(node.left), 0) // drop a negative branch
10 right = max(gain(node.right), 0)
11 best = max(best, left + node.val + right)
12 return node.val + max(left, right)
state
best
-∞
node
–
left
–
right
–
click a step to go back

← → step · space play/pause

Why it works

  1. Every path has one highest node, where it bends: it comes up one side and goes down the other. So it is enough to try each node as that bend, with the best branch down on each side.
  2. A branch with a negative sum only makes a path worse, so max(gain, 0) drops it, and the path simply stops at the node.
  3. Up to the parent goes one side only: a path through the parent that came down here cannot fork into both branches. The two-sided sum goes into best instead.

Complexity

Time O(n): each node is visited once. Memory O(h), where h is the height of the tree: the call stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.