124. Binary Tree Maximum Path Sum

The trap in this one is that a node plays two roles at once, and mixing them up is the classic wrong answer. It’s the hardest of the binary tree DFS problems, but the whole solution is a single postorder traversal that returns one number and updates another — once you see why those two numbers differ, the code writes itself.

The problem

A path here is any chain of connected nodes; it doesn’t have to touch the root, and each node appears at most once. You want the largest possible sum of node values along one such path. Values can be negative, and the path must contain at least one node. (Full statement on LeetCode.)

For a tiny tree with root -10 and children 4 and 6, the best path is just 6 — routing through the root to join both children gives 4 - 10 + 6 = 0, so dragging in the root or the sibling only drops the total.

Intuition: a node bends once, but only sends one branch up

Every path has a single highest node — the point where it stops climbing and turns back down. Call that the path’s peak. At its peak, a path can dip into the left subtree, sit on the node, and dip into the right subtree, forming an upside-down V.

That gives two separate quantities at each node, and keeping them apart is the entire problem:

• The best path peaking here. It can use both children: $\text{node} + \max(\text{left}, 0) + \max(\text{right}, 0)$. This is a candidate for the global answer, but it can’t be handed to the parent — a parent extending through it would create a fork, which isn’t a valid path.
• The best branch to give the parent. A parent can only enter through one side, so the node returns $\text{node} + \max(\text{left}, \text{right}, 0)$ — its value plus at most one downward branch.

The $\max(\cdot, 0)$ is where negatives get pruned: if a subtree’s best contribution is negative, you skip it and take 0 instead of dragging the path down. Because every path peaks at exactly one node, checking the “peak here” value at all $n$ nodes is guaranteed to see the true maximum somewhere.

Solution

The logic is one postorder pass: each node needs both its children’s gains before it can compute its own, so children are finished first. The value that flows up to the parent is a single branch; a running best records the best peak seen anywhere. Written recursively that’s five lines, but a skewed 30,000-node tree can overflow Java’s call stack, so this uses an explicit stack — a Map caches each node’s gain as it’s finalized.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxPathSum(TreeNode root) {
        int best = Integer.MIN_VALUE;
        Map<TreeNode, Integer> gain = new HashMap<>();   // node -> best single-branch sum
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root, lastVisited = null;

        while (node != null || !stack.isEmpty()) {
            while (node != null) {              // dive to the leftmost unprocessed node
                stack.push(node);
                node = node.left;
            }
            TreeNode peek = stack.peek();
            if (peek.right != null && lastVisited != peek.right) {
                node = peek.right;             // right subtree still pending
            } else {
                // Both children are done: drop any branch that would only subtract.
                int left = Math.max(gain.getOrDefault(peek.left, 0), 0);
                int right = Math.max(gain.getOrDefault(peek.right, 0), 0);
                // A path peaking here may use both sides...
                best = Math.max(best, peek.val + left + right);
                // ...but only one side can continue up to the parent.
                gain.put(peek, peek.val + Math.max(left, right));
                lastVisited = stack.pop();
            }
        }
        return best;
    }
}

Seeding best with Integer.MIN_VALUE — not 0 — is what makes an all-negative tree correct: with values like [-3, -2, -1] the answer is -1, and a 0 floor on the global would wrongly report an empty path. The 0 floor belongs only on the branch contributions (the Math.max(..., 0) on each child’s gain), never on the final answer. A null child contributes 0 for free, since getOrDefault returns 0 when it isn’t in the map.

Complexity

	Time	Space
Iterative postorder	$O(n)$	$O(n)$

Each node is pushed and popped once, so time is linear. Space is $O(n)$: the explicit stack holds up to the tree’s height $h$ ($O(\log n)$ balanced, $O(n)$ for a degenerate chain), and the gain map holds one entry per node. A recursive version drops the map for $O(h)$ space but pays that height on the call stack — fine until a skewed tree of tens of thousands of nodes overflows it, which is exactly why the iterative form is the safer default here.

In an interview

Say the two roles out loud before writing anything: “the value I return is a single branch the parent can extend, but the value I record can fork through both children.” That one sentence is what’s being graded — it proves you understand why the returned number and the tracked number are different. Candidates who conflate them either return the two-sided sum (letting parents build illegal forks) or floor the global answer at 0 (breaking all-negative trees). Name both traps and you’ve shown the depth.

This “return a value up, track a global on the side” shape is the crux of the whole binary tree pattern; it’s the same postorder machinery as Maximum Depth of Binary Tree, just carrying a sum instead of a height. If you’ve seen Diameter, the structure will feel familiar — width there, sum here.

References

• LeetCode 124 — Binary Tree Maximum Path Sum