The two-value trick
A path may start and end anywhere and can bend at a node (go up-left, through the node, and down-right). The hard part: what a node returns to its parent is not the same as the best path it can form locally.
Return upward: node.val + max(leftGain, rightGain, 0). A parent can only extend one arm, so you hand it a single straight line. Update global best: node.val + leftGain + rightGain, the full arch that bends here. Clamp negative child gains to 0 so they never drag the answer down.
// per node, bottom-up
L = max(gain(left), 0)
R = max(gain(right), 0)
best = max(best, val + L + R) # arch
return val + max(L, R) # one arm up
L = max(gain(left), 0)
R = max(gain(right), 0)
best = max(best, val + L + R) # arch
return val + max(L, R) # one arm up
Time Complexity
O(N)
One postorder pass; each node computes its gain and updates the global best in O(1).
Space Complexity
O(H)
Recursion stack height H (O(N) for a skewed tree).
Live Visualization
Current call
On active path
Returned gain
Best path so far
Call stack (top = current) — small teal number on each node = gain returned upward
Arch value at each node (val + L + R)
L gain = –
R gain = –
arch here = –
global best = −∞
Step 0 / 0
Left gain
–
clamped ≥ 0
Right gain
–
clamped ≥ 0
Arch here
–
val + L + R
Global best
−∞
answer so far
Hit Play to watch each node return one arm while the global best tracks the best bend.
✓ Done
Speed
Step-by-step trace
| # | Action | Node | L | R | Arch | Returns | Best |
|---|
C++ — Binary Tree Maximum Path Sum (LC 124)
class Solution { int best = INT_MIN; // returns the best straight-down gain starting at node int gain(TreeNode* node) { if (!node) return 0; int L = max(gain(node->left), 0); // clamp negatives to 0 int R = max(gain(node->right), 0); best = max(best, node->val + L + R); // arch that bends here return node->val + max(L, R); // hand parent ONE arm } public: int maxPathSum(TreeNode* root) { gain(root); return best; } };