Binary Tree Maximum Path Sum

Problem (restated)

A path is any node-to-node sequence. Return the maximum sum of node values along any path (at least one node).

Intuition

From each node, best gain you can offer the parent is val + max(0, best child gain). Also consider path through node using both children for the global answer.

Approaches

export 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;
  }
}

export function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const 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));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

export 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;
  }
}

export function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const 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));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

Template connection

Tree DFS return gain + side effect global.

Deep dive

A path can bend through a node using both children, but a value returned to the parent can only include one side (or none). So each DFS call:

1. Computes leftGain = max(0, dfs(left)) and rightGain similarly (drop negative gains).
2. Updates global best with val + leftGain + rightGain (path through this node).
3. Returns val + max(leftGain, rightGain) (best chain upward).

All-negative trees: the best path is the largest single node (gains of 0 never add children).

Reflection

• The value you hand to your parent is one arm: node + max(0, left, right). Both arms cannot climb.
• The best path through this node is the node plus the left gain plus the right gain. A negative arm counts as 0.
• All negative: the answer is the largest single node. If a child shrinks the path, leave it off.