LeetCode 124 – Binary Tree Maximum Path Sum

This is the hardest version of a pattern the track has been building toward since Diameter of Binary Tree: the recursion returns one quantity to its caller while recording a different one. Get those two straight and the solution is twelve lines. Confuse them and no amount of debugging helps, because the code will look right.

The problem

A path is any sequence of nodes connected by edges, in which each node appears at most once. It does not have to pass through the root, and it does not have to end at a leaf. Return the maximum sum of any non-empty path.

    1
   / \        -> 6      the path 2 -> 1 -> 3
  2   3

   -10
   /  \       -> 42     the path 15 -> 20 -> 7, skipping the root entirely
  9    20
      /  \
    15    7

  [-3]         -> -3    a path must be non-empty; the best is the least bad
  [2,-1]       -> 2     take the node alone rather than the negative child

The second example is why the naive "sum everything downward" fails: the best path never touches the root, and the root's value is strongly negative.

The two quantities

At every node, two different things are true and they must not be conflated:

the path that TURNS here     node.val + leftGain + rightGain
    -- uses both children, so it cannot continue upward
    -- this is an ANSWER CANDIDATE

the path that CONTINUES up   node.val + max(leftGain, rightGain)
    -- uses at most one child, so the parent can extend it
    -- this is the RETURN VALUE

A path is a simple path in a tree, so once it descends into both children it has used up its two directions and cannot also go to the parent — the parent would be a third edge at this node. That single geometric fact is why the returned value can only take one side.

So: record the turning path, return the continuing path. Saying that sentence before writing code is the whole problem.

Negative branches are optional

A child that contributes a negative amount should simply not be joined:

leftGain  = max(gain(node.left), 0)
rightGain = max(gain(node.right), 0)

Clamping to 0 means "attach nothing on this side". It handles null children with the same line — gain(null) returns 0 and contributes nothing — so there is no separate null case in the combination step.

Note that clamping does not make the answer non-negative. An all-negative tree still returns its largest single value, because the node's own value is added unclamped.

Java

class Solution {
    private int best;

    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;    // reset: a second call must not see the first's answer
        gain(root);
        return best;
    }

    /** Best sum of a path that starts at `node` and goes DOWN one side,
     *  so the caller can extend it. Records two-sided paths along the way. */
    private int gain(TreeNode node) {
        if (node == null) return 0;

        int left = Math.max(gain(node.left), 0);      // a negative branch is worth skipping
        int right = Math.max(gain(node.right), 0);

        best = Math.max(best, node.val + left + right);   // the path that TURNS here

        return node.val + Math.max(left, right);          // the path that CONTINUES upward
    }
}

best starts at Integer.MIN_VALUE, not 0. Starting at 0 silently encodes "the empty path is allowed and sums to zero", so [-3] would return 0 instead of -3 — the same near-miss as Maximum Subarray, and for exactly the same reason.

The reset in the public method is not decoration. Instance state that survives between calls has already bitten this track twice — an interviewer who invokes your method a second time will find it.

Python

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        best = float("-inf")

        def gain(node: TreeNode) -> int:
            nonlocal best
            if node is None:
                return 0

            left = max(gain(node.left), 0)
            right = max(gain(node.right), 0)

            best = max(best, node.val + left + right)     # turns here

            return node.val + max(left, right)            # continues upward

        gain(root)
        return int(best)

nonlocal best is mandatory. Without it the assignment creates a fresh local on every call, the outer best never changes, and the function returns -inf — no error, no warning, just the wrong answer. It is the single most common way to break this solution in Python, and the same trap as in Diameter.

Using a local closure variable rather than an attribute also means the reuse problem cannot arise: best is created fresh per call.

Complexity

Every node is visited once and does constant work. The maximum path could be anywhere, so no correct algorithm can skip nodes — this is optimal.

O(h) is O(n) on a degenerate tree. Converting to an explicit stack is possible but genuinely awkward here, because the work happens on the way back up: a post-order iterative traversal needs to know whether a node's children have been processed. Say that rather than attempting it under time pressure.

Three ways to carry two answers

The track has now shown all three, which is worth collecting in one place:

Knowing all three means never being stuck when a tree recursion needs more than one number per subtree — which is most of the Hard tree problems.

What the interviewer is checking

• That you separate the returned value from the recorded value, and can say why.
• The geometric reason a path cannot use both children and the parent.
• Clamping negative gains to 0.
• best starting at negative infinity, not 0 — the all-negative tree.
• A single node, and a tree whose best path skips the root.
• nonlocal in Python, or a reset field in Java.
• That you connect it to 543 and 110 rather than treating it as a one-off.