Binary Tree Max Path Sum

Hard tree DP: max path sum anywhere in a binary tree — gain from one child, global answer, and negative-node traps.

advanced3 min readUpdated Aug 4, 2026

dsa
tree
interview
Google
Meta

The problem

A path is any sequence of nodes connected by parent–child edges; each node appears at most once. Return the maximum sum of node values along any path (path can start and end anywhere — not necessarily root-to-leaf).

       -10
       /  \
      9   20
         /  \
        15   7

Best path: 15 → 20 → 7 = 42

Nodes can be negative. Empty path is not allowed — at least one node.

Brute force

Enumerate every pair of nodes as endpoints, compute path sum through LCA. O(n²) paths × O(n) path cost → too slow. Mention and drop.

Core insight

For each node, compute the best contribution you can offer your parent:

gain(node) = node.val + max(0, gain(left), gain(right))

You can only send one side up (a path through parent can’t fork both children upward).

Separately, a path that peaks at this node can use both children:

candidate = node.val + max(0, gain(left)) + max(0, gain(right))

Track global max over all candidates.

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 gain(node: TreeNode | null): number {
    if (!node) return 0;

    const left = Math.max(0, gain(node.left));
    const right = Math.max(0, gain(node.right));

    // path that turns at this node
    best = Math.max(best, node.val + left + right);

    // contribution to parent: at most one child
    return node.val + Math.max(left, right);
  }

  gain(root);
  return best;
}


Time	O(n)
Space	O(h) recursion

Why `Math.max(0, …)`?

A negative child gain only hurts. Treat it as “don’t take that child.” But if the whole tree is negative, best still considers single-node paths because node.val + 0 + 0 is evaluated for every node (init best = -Infinity).

Walk the sample

At 15: gain = 15, candidate = 15
At 7: gain = 7
At 20: left=15, right=7 → candidate 15+20+7=42, gain to parent = 20+15=35
At 9: gain = 9
At -10: left=9, right=35 → candidate 9-10+35=34, gain unused

Global best = 42.

Edge cases

Single node (negative) → that value
All negative → max node value
Straight line tree
Deep recursion — mention iterative postorder if stack limits matter

Common mistakes

Returning only root-to-leaf max
Adding both children to the parent gain (invalid path)
Initializing best to 0 (fails on all-negative trees)
Forgetting Math.max(0, child) and always adding negatives

Interview delivery

Path can be anywhere; nodes may be negative.
Split “gain to parent” vs “path through node.”
Postorder DFS; update global.
Trace all-negative tree.
O(n)/O(h).