Binary Tree Maximum Path Sum

1. Define the problem

A path in a binary tree is any sequence of nodes where each one connects to the next, and no node is used twice. A path does not have to pass through the root . Return the largest possible sum of the values along such a path. The tree arrives as a level-order array such as [-10, 9, 20, null, null, 15, 7], with null for a missing child. Your function builds the tree and returns a single number. Values can be negative, so the answer can be negative too. At each node, work out two different numbers: the best path that turns at this node (left side + node + right side), which is a candidate for the answer, and the best path that continues upward (node + the better one side), which is what the node reports to its parent.

Constraints

The number of nodes is between 1 and 3 × 10⁴
-1000 ≤ node value ≤ 1000
Input is a level-order array with null for a missing child
The path must contain at least one node

Example

Inputvalues = [-10, 9, 20, null, null, 15, 7]

Output42

Explanation The best path is 15 to 20 to 7, giving 15 + 20 + 7 = 42. Going up through the root would add -10, which only makes the total smaller, so the winning path never touches the root.

2. Know the words first

In plain terms

Path: A connected run of nodes in the tree, walking from node to neighbour without repeating any node. It may go up and then back down, but it can only turn once.
Gain: The best total a node can offer its parent: the node’s own value plus the better of its two sides, but never less than the node alone. A side worth less than nothing is simply skipped.
Post-order: Finishing both children before dealing with the node itself. It is the natural order here because a node cannot be scored until both of its sides are known.

3. Visualize the solution

Level-order slots; the label is the node value and the cell shows the gain that node reports upward

-10—

9—

20—

——

15—

7—

Statusinit

The tree is built; no gain has been worked out yet.

What happens in this step

values = [-10, 9, 20, null, null, 15, 7]

Slot 0 holds -10, slots 1 and 2 hold 9 and 20.
Slots 3 and 4 are empty because 9 is a leaf.
Slots 5 and 6 hold 15 and 7.

best starts at -Infinity, so any real path beats it.

Step 1 of 7

Steps to visualize

Each cell is one slot of the tree read level by level; a dash label means the slot is empty.
Gains are worked out from the bottom up, because a node needs both of its children first.
A negative gain is treated as 0 by the parent: it is better to skip that side entirely.
Separately from the gains, a running best keeps the largest turn-at-this-node total seen so far.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Level-order slots; the label is the node value and the cell shows the gain that node reports upward

-10—

9—

20—

——

15—

7—

Statusinit

The tree is built; no gain has been worked out yet.

What happens in this step

values = [-10, 9, 20, null, null, 15, 7]

Slot 0 holds -10, slots 1 and 2 hold 9 and 20.
Slots 3 and 4 are empty because 9 is a leaf.
Slots 5 and 6 hold 15 and 7.

best starts at -Infinity, so any real path beats it.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function maxPathSum(values) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  const root = buildTree(values);
  let best = -Infinity;

  function gain(node) {
    if (node === null) {
      return 0;
    }

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

    best = Math.max(best, leftGain + node.val + rightGain);

    return node.val + Math.max(leftGain, rightGain);
  }

  gain(root);

  return best;
}

Time: O(n)
Space: O(h)

6. Test cases

Test cases

Input	Expected	Covers
`values = [-10, 9, 20, null, null, 15, 7]`	`42`	example from the docstring, the best path skips the root
`values = [1, 2, 3]`	`6`	every value helps, so the path uses the whole tree
`values = [-3]`	`-3`	one node only, and the answer has to be negative
`values = [2, -1]`	`2`	a negative child is left out of the path
`values = [-2, -1]`	`-1`	every value is negative, so the best path is a single node
`values = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]`	`48`	a deeper tree where the path turns at the root

Binary Tree Maximum Path Sum