Binary Tree Maximum Path Sum

LeetCode 124 • Hard • Trees

Input: root = [-10,9,20,null,null,15,7] → Output: 42. Path 15→20→7. DFS: path_through = node + left_gain + right_gain. Return max single-branch.

TimeO(n)

SpaceO(h)

node: — max_sum: —

Current

Path through

node—

left_gain—

right_gain—

max_sum—

Speed:

Ready

Press Play. DFS post-order: path_through = node + left_gain + right_gain. Return node + max(left, right) for parent. Track global max.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Path through node = node + left_gain + right_gain.

═══ BINARY TREE MAX PATH SUM — DFS ═══

PATTERN ▸ DFS with gain + global max O(n) · O(h)

① INIT

max_sum = -inf

② GAIN HELPER

def gain(node): if not node: return 0

left_g = max(0, gain(node.left)); right_g = max(0, gain(node.right))

max_sum = max(max_sum, node.val + left_g + right_g)

return node.val + max(left_g, right_g)

③ RETURN

return max_sum

your implementation

Verify: