Binary Tree Maximum Path Sum

The problem

Given root, the top node of a binary tree with at least one node, return the largest sum that any path in the tree has. A path is a sequence of nodes in which each node is the parent or a child of the one before it, and no node appears twice. It can start and end at any node, it need not include the root, and a single node is a path too. The sum of a path is the total of its nodes' values, which may be negative. Each node has a number val and two children, left and right; a missing child is null.

What to write

type TreeNode = {val:number;left:TreeNode|null;right:TreeNode|null};

function solve(root: TreeNode | null): number

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
6

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

Constraints

The tree is nonempty and values may be negative.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Values can be negative, so a longer path is not always a better one, and the best path may be a single node. The tree is never empty, so there is always at least one path, even when every value is negative.

2. Hint 2: Ask a smaller question

   In the second example the best path is 15, 20, 7. It turns at node 20 and uses both of its children. Could a path that uses both children of 20 also go up to the root? What does that tell you about what 20 can offer its parent?

3. Hint 3: Name the pattern

   Every path has one highest node, and the best path with a given highest node is built from the best downward paths of its two children. Children must answer before their parent: that is postorder tree recursion. Mind that a node reports one thing to its parent and records another as a possible answer. Read the lesson on postorder tree recursion.

4. Hint 4: State the invariant

   Each call returns the largest sum of a path that starts at its node and only goes down. The best path whose highest node is that node is its value plus the results of both sides, where a side with a negative result counts as 0.

5. Hint 5: Sketch the pseudocode

   best = minus infinity. gain(node): for no node return 0. left = the larger of 0 and gain(left child); right = the larger of 0 and gain(right child). best = the larger of best and value + left + right. Return value + the larger of left and right. Call gain(root), then return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Each subtree returns its best one-branch gain. Update the global answer with both nonnegative child gains joined through the node.

The slow way

Try every pair of nodes as the two ends of a path, and every node alone. Walk the path between them and add up its values. It is correct, but n nodes make about n × n / 2 pairs, and one path can hold up to n nodes.

The insight

Every path has one highest node. The path comes up to it from one side and goes down the other, or stops there. So for each node you only need the best downward path on each side. A node gets those from its children, so one walk from the bottom up gives every node its turn as the highest.

Step by step

1. Remember the best path sum found anywhere in the tree. The best path can have any node as its highest, not only the root. The starting value is below every possible sum, so the first real path replaces it even when all values are negative.
2. For each node, find the best path that starts there and goes down. That is the only kind of path a parent can make longer: one of its ends is the child itself, so the parent can be joined on there.
3. An empty subtree adds nothing. A missing child has no nodes to offer, so the most it can add to a path is 0.
4. Ask both sides, and count a side as 0 if its best is negative. A path may stop at this node. When the best downward path on a side has a negative sum, leaving that side out gives more than taking it.
5. The best path that turns at this node joins both sides. A path whose highest node is this one comes up one side, passes through the node and goes down the other, so its best sum is the node's value plus both sides.
6. A path that goes on to the parent can keep only one side. A path cannot fork. If it continues above this node, it reaches the node from the left or from the right, never both, so only the larger side is passed up.
7. Visit every node, then return the best sum found. The call on the root reaches every node, so each node has had its turn as the highest node of a path by the time that call returns.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. Remember the best path sum found anywhere in the tree
  let best = -Infinity;
  // 2. For each node, find the best path that starts there and goes down
  function gain(n) {
    // 3. An empty subtree adds nothing
    if (!n) return 0;
    // 4. Ask both sides, and count a side as 0 if its best is negative
    const l = Math.max(0, gain(n.left)),
      r = Math.max(0, gain(n.right));
    // 5. The best path that turns at this node joins both sides
    best = Math.max(best, n.val + l + r);
    // 6. A path that goes on to the parent can keep only one side
    return n.val + Math.max(l, r);
  }
  // 7. Visit every node, then return the best sum found
  gain(root);
  return best;
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(root: TreeNode | null): number {
  // 1. Remember the best path sum found anywhere in the tree
  let best = -Infinity;
  // 2. For each node, find the best path that starts there and goes down
  function gain(n: TreeNode | null): number {
    // 3. An empty subtree adds nothing
    if (!n) return 0;
    // 4. Ask both sides, and count a side as 0 if its best is negative
    const l = Math.max(0, gain(n.left)),
      r = Math.max(0, gain(n.right));
    // 5. The best path that turns at this node joins both sides
    best = Math.max(best, n.val + l + r);
    // 6. A path that goes on to the parent can keep only one side
    return n.val + Math.max(l, r);
  }
  // 7. Visit every node, then return the best sum found
  gain(root);
  return best;
}

def solve(root):
    # 1. Remember the best path sum found anywhere in the tree
    best = float("-inf")

    # 2. For each node, find the best path that starts there and goes down
    def gain(node):
        # Python needs this line before the helper may change best.
        nonlocal best
        # 3. An empty subtree adds nothing
        if node is None:
            return 0
        # 4. Ask both sides, and count a side as 0 if its best is negative
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        # 5. The best path that turns at this node joins both sides
        best = max(best, node.val + left + right)
        # 6. A path that goes on to the parent can keep only one side
        return node.val + max(left, right)

    # 7. Visit every node, then return the best sum found
    gain(root)
    return best

Example 2, traced

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

Why it works

Every path has exactly one highest node. For that node the best choice is its value plus the best downward path on each side, or nothing on a side where that path is negative. The recursion works this out for every node and keeps the largest result, so no path is missed and no impossible one is counted.

Time and space

Time O(n), extra space O(h). Each node is visited once and does a fixed amount of work, so the time is O(n). The calls that are still waiting for their children, one per level, are the only memory used: O(h) space, where h is the height, the number of levels in the tree.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Pass only the larger side up. With 2 under 1, and 4 and 5 under 2, passing both sides up adds all four nodes together and returns 12, but no path visits all four. The answer is 11.
• Count a side with a negative result as 0. Without that, a root 2 with the single child -1 gives 1 instead of 2, because the -1 is forced into every path through the root.
• Start the best sum below every possible value, not at 0. For a tree that is the single node -3 the answer is -3, and a starting value of 0 would be returned in its place.

Pattern

Postorder tree recursion. Builds on Diameter of Binary Tree.

Keep going