← Back to DSA Animator
Binary Tree Maximum Path Sum LC #124 Hard DFS · Global Max · Gain Tracking
Algorithm
Post-order DFS · Global Max Variable
At every node: leftGain = max(gain(left), 0)  ·  rightGain = max(gain(right), 0)
Update global max with (node.val + L + R). Return node.val + max(L, R) upward.
Examples
Binary Tree
Global Max Tracker
maxSum
-∞
Left Gain
—
Right Gain
—
Waiting for DFS…
Post-order Return Log
NodeL.gainR.gainpathSumreturn
Processing…
State Variables
node.val
—
leftGain
—
rightGain
—
maxSum
-∞
Step Logic —
Start the animation to see step-by-step DFS logic.
🎯
Problem
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge. A node can appear at most once. The path does not need to pass through the root. Given the root of a binary tree, return the maximum path sum of any non-empty path.
Input: root = [1,2,3]
Output: 6
Optimal path: 2→1→3, sum = 6
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Optimal path: 15→20→7, sum = 42
Input: root = [-3]
Output: -3
Single node; max path is -3
1 ≤ nodes ≤ 3×10⁴  |  -1000 ≤ Node.val ≤ 1000
Recursion Stack
Stack empty
Algorithm Steps
Time
O(n)
Space
O(h)
Why It Works

Two key insights:

max(gain, 0) discards negatives path through node uses L+R return only one side up

Negative gains are discarded — if a subtree has a negative contribution, we simply don't include it (clamp to 0).

The path through a node uses both left and right (L + node + R) — this is the candidate for global max. But we can only return one direction to the parent (a path can't fork). The global variable captures the best full path independently of what's returned upward.