Binary tree maximum path sum

Hard TimeO(n) SpaceO(h)

The nodes hold numbers, which may be negative. A path here is any run of connected nodes that bends at most once, so a node may join at most two of its neighbours; it may start and end anywhere, may be a single node, and need not touch the root or run leaf to leaf. Given the tree, return the largest sum along any such path. A longer path is not always a better one.

Examples

Example 1

Input
root = buildTree()
Output
25
3 → 2 → 4 → 7 → 9 sums to 3 + 2 + 4 + 7 + 9 = 25, bending once at the root.

Example 2

Input
root = { val: -10, left: { val: 9, left: null, right: null }, right: { val: 20, left: { val: 15, left: null, right: null }, right: { val: 7, left: null, right: null } } }
Output
42
15 → 20 → 7 sums to 42; carrying on up through the -10 would only lose.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function maxPathSum(root) {
  let best = -Infinity;
  function gain(node) {
    if (node === null) return 0;
    const left = Math.max(gain(node.left), 0);
    const right = Math.max(gain(node.right), 0);
    const through = node.val + left + right;
    if (through > best) best = through;
    return node.val + Math.max(left, right);
  }
  gain(root);
  return best;
}
maxPathSum(buildTree());
Done

The first 9 calls, of 17. This one does not fit on a page.

Step through maxPathSum(buildTree()) call by call

More like this

All binary trees examples (9) →