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

• Which pattern gave this away within 90 seconds?
• What changed from the standard template?
• What would break the current solution?