Binary Tree Maximum Path Sum
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Find the largest sum of any path in the tree (a path goes along parent-child links, does not have to touch the root, and visits each node at most once). Values can be negative.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1A path that bends at a node uses the node plus the best downward path on each side. What if a side is negative?
- Hint 2What can you tell the parent? Only a straight path down one side.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You are choosing the most profitable stretch of a road network shaped like a tree, where some road segments lose money. At each junction you ask each branch: "what is the most I can gain by going down your way?" Branches that lose money are simply not taken (gain 0). The best trip bending at this junction is junction + left gain + right gain. But the branch above can only be told about ONE direction: junction + the better of the two gains.
- The obvious way
Compute the best path through every node separately by exploring both subtrees each time: O(n²).
- The key insight
Write a function gain(node) = the best sum of a path that starts at this node and goes DOWN one branch (at least the node itself; negative sides are dropped, i.e. use max(0, gain(child))). While computing it, also check the bend: node + left gain + right gain, and keep the best seen. The function returns node + the bigger side gain to the parent.
- The algorithm
- best = very small. gain(empty) = 0.
- At a node: left = max(0, gain(left child)), right = max(0, gain(right child)).
- The path bending here is node + left + right: update best.
- Return node + max(left, right) to the parent. The answer is best.
Watch it run
Exampletree = [-10, 9, 20, null, null, 15, 7]
Leaf 9: gain 9; the best path so far is 9.
best 9
Where people slip
- Start best at negative infinity, not 0: an all-negative tree must return its largest (least negative) value.
- Return only ONE side to the parent: a path cannot fork upward.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def max_path_sum(root):
best = float("-inf")
def gain(node): # best path starting here, going down one side
nonlocal best
if node is None:
return 0
left = max(0, gain(node.left)) # drop a side that loses money
right = max(0, gain(node.right))
best = max(best, node.val + left + right) # the path that bends at this node
return node.val + max(left, right) # only one side can continue upward
gain(root)
return bestNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.