Binary Tree Maximum Path Sum

Given the root of a binary tree, return the maximum path sum of any non-empty path.

A path is any sequence of nodes connected by edges, where each node appears at most once; it need not pass through the root. The path sum is the sum of the nodes' values. Node values may be negative.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

For each node, the best path bending at it is node.val + best-left-gain + best-right-gain.

Clamp a negative child gain to 0 — an unhelpful branch should simply be dropped.

Return node.val + max(leftGain, rightGain) upward, but record node.val + leftGain + rightGain globally.

Common doubts

A branch with negative total only reduces the path sum, so it's better to stop and not include it — contributing 0.

The path is non-empty and all values can be negative, so the best path might be a single negative node; 0 would be wrong.

Same return-one-record-both structure, but you sum node values (with a 0-clamp) instead of counting edges.

Interview follow-ups

· What an interviewer asks next.

Remember which node achieved the maximum and its two chosen branches, then walk down both sides from it.

You'd only evaluate the bending path at the root: root.val + max(0, gain(left)) + max(0, gain(right)).

Fun facts

Maximum path sum and tree diameter are the same algorithm with a different quantity combined at each node.
The 0-clamp is exactly Kadane's 'reset when the running sum goes negative', lifted onto a tree.

Asked at

AmazonFacebookMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 2, 3]
Output: 6
The path 2 -> 1 -> 3 sums to 6.

Example 2

Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42
The path 15 -> 20 -> 7 sums to 42; going up to -10 would only reduce it.

Constraints

- The number of nodes is in the range [1, 3 * 10^4] - -1000 <= Node.val <= 1000

This is the diameter pattern with values instead of edge counts, plus one twist: a negative branch should be dropped (contribute 0) rather than dragging the sum down. Each call returns the best single downward path (clamped at 0), while recording the best path that bends at the node — node.val + leftGain + rightGain.

Prerequisites

Before you start

· Concepts used directly in the solution.

Postorder recursion. Combine children's results at the parent, bottom-up.

Return vs record. Return one clamped branch upward; record both branches into a global maximum.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Can the path be a single node?”

Yes — the path is non-empty, so the answer can be a lone (possibly negative) node.

“Can values be negative?”

Yes, which is why negative branches are clamped to 0 before combining.

The ideal opening — say it like this

For each node, the best path bending at it is the node's value plus the best downward gain from each side, where a negative side contributes zero.

Each call returns the value plus its single best downward branch so the parent can extend it, while I keep a global maximum of the bending paths.

Understand the problem

Worked example — tree [-10, 9, 20, null, null, 15, 7]

       -10
       /  \
      9    20
          /  \
         15    7
gain(15)=15, gain(7)=7 -> at 20: bend = 20+15+7 = 42  (best)
at -10: l=max(9,0)=9, r=max(gain(20)=20+15=35,0)=35 -> bend = -10+9+35 = 34
answer: 42

Key observations

1Aha

Clamp negative branches to 0

A branch with a negative gain only reduces the sum, so treat it as unused (0) rather than subtracting.

2Aha

Bend records both, return extends one

The global answer can use both children (a path bending at the node); the value passed up can extend only a single branch.

3Aha

Start the answer at -infinity

Because a single negative node can be the best path, initialize the global maximum below any possible value.

Brute force vs optimal

	Recompute gains per node	Single-pass gain + record
Idea	At each node, recompute both downward gains	One postorder pass; record bend, return one branch
Time	O(n^2)	O(n)
Space	O(height)	O(height)

The single-pass version reuses each gain. Full code is in the Approaches selector below.

Summary

Key takeaway

For each node, the bending path is node.val + max(gainL, 0) + max(gainR, 0); record it globally and return node.val + max(gainL, gainR, 0) upward. Start the answer at −∞. O(n) time, O(height) space.

gain(node):
    if node is null: return 0
    l = max(gain(node.left), 0)
    r = max(gain(node.right), 0)
    best = max(best, node.val + l + r)
    return node.val + max(l, r)