#137

Binary Tree Maximum Path Sum

hard

dynamic-programmingtreedepth-first-searchbinary-tree

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 parent–child edges; it need not pass through the root, and each node appears at most once. A path can turn at one node (going down its left side and up into its right side) but cannot branch at two nodes. The sum is the total of the values on the path.

The tree is given as a level-order array where null marks a missing child: [-10, 9, 20, null, null, 15, 7].

Example

Input: root = [1,2,3]213

Output: 6

2 → 1 → 3 sums to 6.

Constraints

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

Intuition

A path is any chain of nodes connected by parent–child edges; it can start and end anywhere and may turn at a single node (rise up one child, peak, descend the other). We want the maximum sum over all such paths. A brute force fixes each node as the path's peak and explores the best downward run on each side.

function maxPathSum(root) {
  let best = -Infinity;
  // Best sum of a straight downward path starting at node.
  const downward = (node) => {
    if (!node) return 0;
    const left = Math.max(0, downward(node.left));
    const right = Math.max(0, downward(node.right));
    return node.val + Math.max(left, right);
  };
  // Try every node as the path's turning point (peak).
  const visit = (node) => {
    if (!node) return;
    const left = Math.max(0, downward(node.left));
    const right = Math.max(0, downward(node.right));
    best = Math.max(best, node.val + left + right);
    visit(node.left);
    visit(node.right);
  };
  visit(root);
  return best;
}

Brute force — for every node, recompute the best downward arm on each side: O(n²).

This recomputes downward from scratch at every node — O(n²). Can we fuse the two passes?

The key observation: the downward gain a node needs is computable bottom-up in the same traversal that updates the global best. So do one post-order pass where each call returns node.val + max(0, leftGain, rightGain) — the most it can contribute to a parent, which can only descend through one child. Separately, before returning, update a global best with node.val + leftGain + rightGain — the best path that turns at this node and uses both children. Clamping each side at 0 drops a negative arm.

Tracing [-10, 9, 20, null, null, 15, 7]:

Leaves 9, 15, 7 return their own values as downward gains (9, 15, 7).
At node 20: turn-here candidate is 20 + 15 + 7 = 42 → updates the global best to 42. It returns 20 + max(15, 7) = 35 upward.
At the root -10: turn-here candidate is -10 + max(0, 9) + max(0, 35) = 34 — less than 42. The negative root can't improve on the 15 → 20 → 7 path, so the answer stays 42.

The model bridge: the recursion returns a one-sided downward gain (what a parent can use), while the answer tracks a two-sided turn-here sum in the global best — two distinct quantities computed at the same node.
Clamping negatives at 0 (Math.max(0, gain)) is how a subtree that would only hurt the sum is dropped — equivalent to not extending the path into it.
There's no lane: the value flows up the recursion and a global is updated as a side effect, which a single scanned row can't represent.

Optimization

Post-order with a running best

For each node, compute the best downward gain — the most you can collect starting at this node and going straight down one side: node.val + max(0, leftGain, rightGain) (a negative side is dropped by clamping at 0). That value is what the node can contribute upward to its parent, since a parent's path can only descend through one of its children.

But a path may turn at this node — descending its left side and rising into its right. So separately track the global best as node.val + max(0, leftGain) + max(0, rightGain), which is the best path whose highest point is this node. The answer is the maximum of that quantity over all nodes.

O(n) time (one post-order pass), O(h) recursion space.

function maxPathSum(root) {
  let best = -Infinity;
  // Returns the max downward gain starting at node (the value usable by its parent).
  const gain = (node) => {
    if (!node) return 0;
    // Drop a negative subtree: contributing it would only shrink the path.
    const left = Math.max(0, gain(node.left));
    const right = Math.max(0, gain(node.right));
    // A path that turns at this node uses both sides; update the global best.
    best = Math.max(best, node.val + left + right);
    // Upward, a parent can only take one side.
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

Complexity analysis

Time complexity: O(n). Here's why:

One post-order pass; each node returns its downward gain and updates the global best in O(1).

So O(n), fusing the brute force's two O(n) passes (which made it O(n²)) into one.

Space complexity: O(h). Here's why:

Only the recursion stack — depth h.

O(log n) balanced, O(n) for a chain. The single best accumulator is O(1).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = [7]7	7	A single node — the path is just itself.
root = [-5]-5	-5	All-negative: a non-empty path must take the one node.
root = [-8,-3]-3-8	-3	Best is the lone less-negative node, not the sum.
root = [4,5,6]546	15	The path turns at the root: 5 → 4 → 6.
root = [3,-4,-5]-43-5	3	Both children are negative and dropped; the root alone wins.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor