Binary Tree Maximum Path Sum

Examples

Input: root = [1,2,3]
Output: 6

The path 2 -> 1 -> 3 uses every node and sums to 6, which is the best available.

Input: root = [-10,9,20,null,null,15,7]
Output: 42

The best path is 15 -> 20 -> 7, entirely within the right side of the tree, summing to 42. It doesn't touch the root at all, since -10 would only drag the sum down.

Constraints

• The number of nodes is in the range [1, 3 * 10^4].

• Node values are in the range [-1000, 1000].

Approach

Every possible path has exactly one highest point — the node where it stops going up one side and starts going down the other (a path can also just go straight down one side, which is the same idea with one side contributing nothing).

For a candidate "highest point," the best path through it is: its own value, plus the best downward-only sum from its left child, plus the best downward-only sum from its right child (treating either side as 0 if going into it would only hurt). The tricky part is that a node can only pass one of those two downward sums up to its own parent, since a path can't branch in two directions and still continue upward.

Solutions

Brute Force — Recompute Downward Sums at Every Node

Write a helper maxDownward(node) that returns the best sum you can get starting at node and going straight down through one child (clamped to 0, since it's always fine to skip a branch that would only subtract).

Then, for every node in the tree, treat it as the path's highest point: its value plus maxDownward of its left child plus maxDownward of its right child. Take the best value found over every node. This is correct, but maxDownward gets recomputed from scratch for every node it's called on, redoing a lot of work.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxPathSum(root) {
  function maxDownward(node) {
    if (node === null) return 0;
    return Math.max(0, node.val + Math.max(maxDownward(node.left), maxDownward(node.right)));
  }

  function maxThroughNode(node) {
    if (node === null) return -Infinity;
    const throughThisNode = node.val + maxDownward(node.left) + maxDownward(node.right);
    return Math.max(throughThisNode, maxThroughNode(node.left), maxThroughNode(node.right));
  }

  return maxThroughNode(root);
}

Time: O(n^2) — maxDownward re-walks a subtree from every node above it · Space: O(h) — recursion stack, where h is the tree's height

Optimal — Single Pass with a Running Global Maximum

Do a single post-order traversal (children before parent). The recursive function returns the best downward-only sum through a node — exactly what a parent needs to extend a path upward. But while computing that, at every node it also checks the best "bend here" path (value + both children's downward sums) and updates one shared running maximum. That running maximum is never returned to the caller — it only gets read at the very end — so every node's contribution is computed exactly once.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxPathSum(root) {
  let maxSum = -Infinity;

  function maxDownward(node) {
    if (node === null) return 0;

    const leftGain = Math.max(0, maxDownward(node.left));
    const rightGain = Math.max(0, maxDownward(node.right));

    maxSum = Math.max(maxSum, node.val + leftGain + rightGain);

    return node.val + Math.max(leftGain, rightGain);
  }

  maxDownward(root);
  return maxSum;
}

Time: O(n) — every node is visited exactly once · Space: O(h) — recursion stack, where h is the tree's height