DSA AnimatorDSA animations
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.

How to solve Binary Tree Maximum Path Sum

LeetCode 124 · Hard · Tree · Pattern: DFS Gain

Why the obvious approach is slow

Trying every pair of end points and summing the path between them is far too slow. Instead, each node can report the best downward path it can offer to its parent.

The key idea

Define the gain of a node as its value plus the better of its two downward gains. A negative gain only hurts, so treat it as 0. At each node, the best path that bends here is its value plus the left gain plus the right gain. Update a global best with that bending path. But return only one side to the parent, because a path cannot split in two.

Remember

Record the bending path, but return a single branch. Clamp negative gains to 0.

Run the animation above on your own input, or watch the 2:10 video explanation of Binary Tree Maximum Path Sum with a dry run and Java code.

More Tree problems