Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Binary Tree Maximum Path Sum

LeetCode #124Hard
Post-order gains · clamp negative arms

Given the root of a binary tree, return the maximum sum of any non-empty path. A path is a sequence of connected nodes and need not pass through the root.

Asked atAmazonMetaMicrosoft
step 1 / 17
binary tree (values may be negative)
9
-10
15
20
7
call stack ↓
(returned)
Recursive DFS (post-order gain + global max)
▸
1best = −∞
2gain(node):
3    if node is null: return 0
4    L = max(gain(node.left),  0)   // drop negative arms
5    R = max(gain(node.right), 0)
6    best = max(best, node.val + L + R)   // bend here
7    return node.val + max(L, R)          // extend parent
8// answer = best
state
  • goalmax path sum
  • global best−∞

line 1A PATH is any chain of connected nodes; its sum is the sum of values, and it may start and end anywhere — it does not have to touch the root. Insight: every path bends at exactly one TOP node. One post-order pass: each call returns the best single-arm GAIN going down, and along the way we update a global best with the full bend = node + leftGain + rightGain.