Binary Tree Maximum Path Sum

The problem

You are given the root of a binary tree whose values can be negative. A path is a chain of nodes where each pair of neighbors in the chain is joined by an edge, and no node appears twice. A path has at least one node. It does not have to pass through the root, and it may go up and then down again.

Return the largest sum of values along any path.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [-3, 9, 4, null, null, 5, -2]

Output: 15

The path 9, −3, 4, 5 sums to 15. It passes through the negative root, because 9 on one side and 4 + 5 on the other are worth much more than 3.

Example 2

Input: root = [2, -1, 3]

Output: 5

The path 2, 3 sums to 5. Adding −1 would only lower it.

Example 3

Input: root = [-4]

Output: -4

A path needs at least one node, so the answer is −4 even though it is negative.

Constraints

• The tree has n nodes, where 1 ≤ n ≤ 30,000.
• -1,000 ≤ Node.val ≤ 1,000

Clarifying questions

Must the path go through the root?

No. It can sit anywhere in the tree.

Can the path go up and then down?

Yes, but only once. It climbs to one highest node and goes down from there. It cannot branch.

Can the answer be negative?

Yes. If every value is negative, the answer is the largest single value.

Can the path be empty?

No. It holds at least one node, so 0 is not a safe starting value for the answer.

Spot the pattern

Every path has exactly one highest node, where it bends. From there it goes down the left side, the right side, both, or neither. So if each node knew the best downward path on each side, it could score the best path that bends at itself. Asking children first and then combining is a tree traversal in post-order: each subtree hands one number up.

Solutions

One post-order passO(n)

Show all

There is only one approach worth showing. Listing every path is far slower, and every node must be seen anyway, which is what this single pass does.

One post-order pass O(n)

The idea

Each call of gain(node) answers one question: what is the best sum of a path that starts at this node and goes down one side? That is the node’s value plus the better of its two children’s gains.

If a child’s gain is negative, taking that side only lowers the sum. So we cut it to 0, which means “do not go that way”.

Before returning, the node also tries itself as the bend: the left gain, plus the node, plus the right gain. That is the best path whose highest node is this one. We keep the largest such sum in best.

The return value and the score are different on purpose. A path that goes on up to the parent cannot use both sides, because it would branch. So the node returns only one side, but scores both.

Why it never misses the answer: every path has one highest node, and every node is tried as the highest node once, with the best possible left and right parts below it.

Walkthrough

best

−∞

call stack top →

empty

1. best = -inf
2. def gain(node):
3. if node is None: return 0
4. left_gain = max(gain(node.left), 0)
5. right_gain = max(gain(node.right), 0)
6. best = max(best, node.val + left_gain + right_gain)
7. return node.val + max(left_gain, right_gain)
8. gain(root)
9. return best

Each call answers: what is the best sum of a path that starts here and goes down one side? It also tries this node as the top of a path. best starts at −∞. Under a finished node, ↑ shows the gain it sends up.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // At least one node is always taken, so start below any real sum.
    private int best = Integer.MIN_VALUE;

    // One post-order pass. Each node returns its best downward gain, and
    // tries itself as the top of a path. One call per node, so n steps.
    public int maxPathSum(TreeNode root) {
        gain(root);
        return best;
    }

    // The best sum of a path that starts at node and goes down one side.
    private int gain(TreeNode node) {
        if (node == null) return 0;
        // A side that only lowers the sum is better left out.
        int leftGain = Math.max(gain(node.left), 0);
        int rightGain = Math.max(gain(node.right), 0);
        // A path can bend here once: down the left, up, down the right.
        best = Math.max(best, node.val + leftGain + rightGain);
        // A path that goes on upward can only use one side.
        return node.val + Math.max(leftGain, rightGain);
    }
}

Big O

Time O(n)Space O(h)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop. The work repeats through recursion, so we count the calls of gain. Each call does a fixed job: two calls, two max with 0, one sum, one update of best and one return. So each call counts as 1 step.

   1. best = -inf
   2. def gain(node):
   3. if node is None: return 0
   4. left_gain = max(gain(node.left), 0)
   5. right_gain = max(gain(node.right), 0)
   6. best = max(best, node.val + left_gain + right_gain)
   7. return node.val + max(left_gain, right_gain)
   8. gain(root)
   9. return best

2. 2 Count the runs on Example 1

   Example 1 has 5 nodes, and each gets one call. The three leaves 9, 5 and −2 each call their 2 empty children, which return 0 at once.

   5 node calls + 6 empty calls = 11 calls.

   total calls

   5 nodes + 6 empty children = 11

3. 3 Write the count for any n

   Every node gets one call. A binary tree with n nodes has n + 1 empty child spots, and each gets one call:

   n + (n + 1) = 2n + 1 calls

   Check it with Example 1: 2 × 5 + 1 = 11.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. One extra call does not change the growth.
   • Drop the 2. When n doubles, 2n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps one number, best, plus left_gain and right_gain in each call. The calls that wait on the call stack form one path from the root down, so there are at most h, the height of the tree. A balanced tree has h about log n, and a chain has h = n. So the space is O(h).

   bestcall stack (one frame per level)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 30,000 nodes, that is 30,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Common mistake

Returning both sides to the parent

Returning node.val + left_gain + right_gain lets the parent build a path that branches into three directions, which is not a path. Score both sides at the node, but return only the better one.

Tested at the limits

2,000 random trees of 1 to 9 nodes, mostly with negative values, so the best path is often short or a single node. The one post-order pass gave the same answer every time as a slow check that walks out from every node and tries every path.

Largest inputs	Result
30,000 nodes (the most allowed), balanced. One post-order pass.	0.006 s, and under 0.01 MB of extra memory: only about 15 calls wait at once.
30,000 nodes in one long line. One post-order pass.	0.01 s, and about 4 MB of extra memory: 30,000 calls wait at once, one per level, which is the O(h) space.