Binary Tree Maximum Path Sum

1. Problem & Core Objective

A path is any sequence of nodes connected by edges, where each node appears at most once. It need not pass through the root. Return the maximum sum of the values along any path.

      -10
      /  \
     9    20        →  42   (the path 15 → 20 → 7)
         /  \
        15   7

Constraints: 1 <= nodes <= 3 × 10^4 · -1000 <= Node.val <= 1000 · values may be negative

What's actually being tested: the return-versus-record split from question 3, now with negative numbers — which adds a second idea: a subtree that would hurt you should be skipped entirely, clamped to a contribution of zero. If you understood Diameter, this is Diameter with arithmetic and one clamp.

2. First-Principles Thought Process

Anchor on the highest node, as in Diameter

Every path has a unique topmost node. Anchored there, the path is:

best downward path into the left + node's value + best downward path into the right

So evaluate that at every node and take the maximum.

The same asymmetry as Diameter

A path that descends left, crosses the node, and descends right has used both branches — it cannot continue up to the parent.

So again there are two different quantities:

What's new: negatives mean you can skip

In Diameter, more edges was always better. With negative values it isn't — a subtree summing to −7 should simply not be included.

Since a path may stop at any node, including nothing from a subtree is always a legal option. So clamp each child's contribution at zero:

int L = Math.max(gain(node.left),  0);
int R = Math.max(gain(node.right), 0);

max(gain, 0) reads as: take this subtree if it helps, otherwise take nothing from it.

Why the answer isn't clamped

The recorded candidate is node.val + L + R, and node.val is not clamped — every path must contain at least one node, so you can't skip the node you're standing on.

That's what makes an all-negative tree work: the answer is the single largest (least negative) node, which is found when that node is the anchor with L = R = 0.

Initialize the running best to Integer.MIN_VALUE, not 0 — otherwise an all-negative tree wrongly returns 0.

3. Solution Paths

Approach 1 — Try every node as the anchor, recomputing downward sums (brute force)

public int maxPathSum(TreeNode root) {
    if (root == null) return Integer.MIN_VALUE;
    int through = root.val + Math.max(maxDown(root.left), 0)
                           + Math.max(maxDown(root.right), 0);
    return Math.max(through, Math.max(maxPathSum(root.left), maxPathSum(root.right)));
}

private int maxDown(TreeNode n) {           // best single downward path from n
    if (n == null) return 0;
    return n.val + Math.max(0, Math.max(maxDown(n.left), maxDown(n.right)));
}

• Time O(n²) worst case · Space O(h)

Counter-questions on this approach

⭐ "Where's the O(n²)?"

maxDown is called at every node and re-walks that node's entire subtree. On a degenerate tree that's n + (n−1) + … = O(n²); at 3 × 10^4 nodes, about 4.5 × 10^8 — too slow.

It's the identical redundancy to question 3: the downward sums are already being computed by the traversal and then discarded.

⭐ "So what's the fix?"

Compute each downward gain once, bottom-up, and record the through-path candidate at the same moment both children's gains are in hand. One pass, O(n).

"Why does maxPathSum return Integer.MIN_VALUE for null rather than 0?"

Because 0 isn't a valid path sum — every path has at least one node, so on an all-negative tree the answer must be negative. Returning 0 would let an empty path win. It's the same reason the running best is seeded with MIN_VALUE.

Approach 2 — One traversal: return the gain, record the best (optimal)

private int best;

public int maxPathSum(TreeNode root) {
    best = Integer.MIN_VALUE;          // NOT 0 — the answer can be negative
    gain(root);
    return best;
}

private int gain(TreeNode node) {
    if (node == null) return 0;

    int L = Math.max(gain(node.left),  0);    // clamp: skip a harmful subtree
    int R = Math.max(gain(node.right), 0);

    best = Math.max(best, node.val + L + R);  // RECORD: path THROUGH node
    return node.val + Math.max(L, R);         // RETURN: path DOWN from node
}

Trace — [-10,9,20,null,null,15,7]:

Answer 42 ✓ — and note the winning path never touches the root.

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "Why clamp the children's gains at 0 but not node.val?"

Because a path may stop at any node, so contributing nothing from a subtree is always allowed — max(gain, 0) expresses "include this side only if it helps".

But every path must contain at least one node, and when I'm anchored at node, that node is in the path by construction. Clamping node.val would let me exclude the node from its own path, which is meaningless — and it would break all-negative trees, since the answer there is a single negative node.

⭐ "Why is best initialised to Integer.MIN_VALUE and not 0?"

Because the answer can be negative. On a tree of all negative values — say [-3] — the correct answer is −3, the least-bad single node. Starting at 0 would return 0, which corresponds to the empty path and isn't legal.

It's the same class of error as the clamp question: 0 is only a valid floor for things you're allowed to skip.

⭐ "Why does the returned value use max(L, R) while the recorded one uses L + R?"

Because they answer different questions. The recorded value is the best path through this node, which may descend into both children — that path is complete and can't go further up. The returned value is what the parent can extend, and a parent can only attach to a path that comes up one side.

A path can't enter a node from the parent and leave through both children; it would visit the node twice.

"Can node.val + L + R overflow?"

Not here. Values are bounded by 1000 and there are at most 3 × 10^4 nodes, so the largest possible sum is 3 × 10^7 — comfortably inside int. If the bounds were larger I'd use long. Worth checking rather than assuming, since the sum is over a path, not a single value.

"The mutable field again — is that acceptable?"

Same trade as question 3. It's non-reentrant, so I reset it at the start. The cleaner alternative is returning a record (gain, bestSoFar), which makes explicit that the recursion produces two values. I'd mention it.

"What about stack depth at 3 × 10^4?"

A degenerate tree gives 30,000 frames, which is a real overflow risk on the default JVM stack. The fix is an explicit postorder stack with a map from node to gain — same complexity, frames on the heap.

Comparison

4. Why the Optimal Wins

The brute force recomputes every downward sum once per ancestor. The optimal computes each once and records the through-path candidate at the only moment it's free — when both children's gains are in hand.

But the real content is the two ideas working together:

1. Return ≠ record. The answer at a node isn't extendable upward, so return what the parent can use and record the answer separately.
2. Clamp what you can skip. max(gain, 0) turns "should I include this subtree?" into arithmetic, with no branching.

The framing worth keeping:

Return val + max(L, R), record val + L + R, and clamp only the parts you're allowed to omit.

The clamp is the transferable half. Any optimisation where a component is optional becomes max(component, 0) — it appears again in Kadane's algorithm and throughout 1-D DP.

5. Java Prerequisites

The clamped split

int L = Math.max(dfs(node.left),  0);
int R = Math.max(dfs(node.right), 0);
best  = Math.max(best, node.val + L + R);   // record — both sides
return node.val + Math.max(L, R);           // return — one side

Sentinel initialization. Integer.MIN_VALUE for a maximum that may be negative; 0 only when the empty case is genuinely valid.

Overflow discipline. Adding several MIN_VALUEs overflows to positive. It can't happen here because the clamp guarantees L, R >= 0 and best is only ever compared, never added to. Worth confirming rather than assuming.

Reset instance state in the public method.

6. Interview Communication Guide

Clarifying questions: Must the path pass through the root (no)? Can a path be a single node (yes — important for all-negative trees)? Can values be negative (yes — this is the crux)? Is the path a simple downward path or can it turn (it can turn — that's what makes it a "path" rather than a root-to-leaf sum)?

The pitch

"Every path has a unique topmost node, so I anchor there: the best path through a node is its value plus the best downward path into each child.

Just as in the diameter problem, there are two different quantities. The best path through a node uses both children and can't be extended to the parent — a path can't enter from above and leave through both children without visiting the node twice. So the parent can only use a path coming up one side.

That means the recursion returns val + max(L, R) and records val + L + R into a running maximum.

What's new here is negatives. A subtree that sums to something negative should just be skipped — and since a path can stop at any node, skipping is always legal. So I clamp each child's gain with max(gain, 0): include it if it helps, otherwise contribute nothing.

I do not clamp node.val, because every path contains at least one node and I'm anchored on this one. That's what makes all-negative trees work — the answer is the single least-negative node, found when it's the anchor with both gains clamped to zero.

And I seed the running best with Integer.MIN_VALUE, not 0, for the same reason: 0 corresponds to the empty path, which isn't a legal answer.

O(n) time, O(h) stack. At 3 × 10^4 a degenerate tree gives 30,000 frames, so I'd use an explicit stack if depth were a concern."

Edge cases to volunteer:

Name [-3] and [-2,-1]. Both are where the clamp and the MIN_VALUE seed earn their place — a solution that starts best at 0 returns 0 for both and passes almost everything else.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual path, not just the sum."

Track, alongside each gain, the node that achieved it. When a new best is recorded, store the anchor plus its two best-child directions, then walk down each side following the stored choices. O(n) still, but the bookkeeping roughly triples — same trade as reconstructing the diameter's path.

⭐ "Restrict paths to root-to-leaf only."

Much easier. The turning is what makes this problem hard; without it there's no return-versus-record split at all. Just max over leaves of (sum along the path), computed by carrying the running sum down — the direction from question 10.

"What if all values were guaranteed non-negative?"

The clamp becomes a no-op, since every gain is already >= 0, and best could safely start at 0. The problem collapses to diameter-with-weights. Worth noting that the negative values are precisely what makes this Hard rather than Medium.

"Paths must contain at least k nodes."

Substantially harder — the clamp is no longer valid, because you may be forced to include a negative subtree to meet the length requirement. You'd need to carry (length, bestSum) pairs and track the best for each length up to k, which turns it into a DP over the tree at O(n·k).

"Do it for an n-ary tree."

Record val + (the two largest clamped child gains), return val + (the single largest). Track the top two as you loop over children, exactly as in the n-ary diameter follow-up. A clean generalisation, and a good check of whether the pattern was understood.

"What if the tree had 10^6 nodes in a chain?"

Recursion overflows. Convert to an explicit postorder stack with a map from node to gain. Same O(n) time, frames on the heap where the size is yours to set.