5.3 Path Sum

Demo: Binary Tree Maximum Path Sum — LC 124 (Hard — Microsoft/Meta High)

Statement (Demo): Given the root of a binary tree, return the maximum sum of any path from any node to any node (a single node counts). A path cannot visit a node twice. Example: root=[-10,9,20,null,null,15,7] → 42 (15→20→7) | ⚡ n ≤ 3×10⁴, -1000 ≤ val ≤ 1000

Approach: Two numbers at every node: (1) the path that bends here = node + leftGain + rightGain → updates the global best; (2) only one side can go up to the parent = node + max(leftGain, rightGain). Never take a negative branch (max(gain, 0)).

function maxPathSum(root) {
  let best = -Infinity;
  const gain = (node) => {
    if (!node) return 0;
    const left = Math.max(gain(node.left), 0); // drop negative branches
    const right = Math.max(gain(node.right), 0);
    best = Math.max(best, node.val + left + right); // bend here
    return node.val + Math.max(left, right); // one side to the parent
  };
  gain(root);
  return best;
}

Complexity: Time O(n), Space O(h) recursion