Binary Tree Maximum Path Sum

HardTreesTreeDFSBinary TreeDynamic Programming

Problem

A path in a binary tree is a sequence of nodes connected by parent-child edges with no repeated node; it need not start at the root or end at a leaf, and it may bend once, going from one child up into a node and back down into the other. Find the largest sum along any path.

Example. For a tree with root -10, left child 9, and right child 20 (children 15 and 7), the best path is 15 → 20 → 7, summing to 42; the root is left out because including it would only lower the total.

Key idea

Checking every possible path directly is wasteful, since paths overlap heavily. Instead, define for each node its best downward contribution: the largest sum starting there and continuing into at most one child, computed bottom-up. That is the node's value plus whichever child's contribution is larger, with a negative contribution clamped to zero, since a subtree should only count when it helps.

While computing this, also evaluate a candidate that lets the path bend at that node: its value plus both children's contributions, each clamped to zero. Track the largest such candidate as the final answer. The value returned to a parent must stay the single-branch version, since a real path cannot pass through a node twice.

Solution

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

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;

  function contribution(node: TreeNode | null): number {
    if (node === null) {
      return 0;
    }

    // Clamp negative contributions to zero, since a subtree should only count when it helps.
    const left = Math.max(contribution(node.left), 0);
    const right = Math.max(contribution(node.right), 0);

    // A path bending at this node can use both children at once; only valid as a candidate answer.
    const bentPath = node.val + left + right;
    best = Math.max(best, bentPath);

    // A parent can only extend one branch, so return the better single-branch chain.
    return node.val + Math.max(left, right);
  }

  contribution(root);
  return best;
}

Complexity

  • Time: O(n). One post-order visit per node.
  • Space: O(h). The recursion stack, bounded by the tree's height.

Watch out for

  • Clamp negative child contributions to zero, but always include the node's own value, even when negative.
  • Return only the single-branch value to the parent; the bent-path value would let a path effectively reuse a node.
  • Initialize the running best to a very small value, since the optimal path may be one negative node if every neighbor is worse.

Pattern

This is a "return one thing, track another" tree dynamic-programming shape: the return value supplies what a parent needs, a single chain, while a side variable accumulates the true answer. The same shape appears in computing the diameter of a binary tree.

Related questions