Maximum path sum with negative values

Why this matters

A path in a tree is a list of nodes where each node is joined to the next by an edge, which is a link between a parent and a child. You can start at any node and end at any node. The sum of a path is the total of the values of the nodes on it. This lesson asks for the largest sum of any path in a binary tree.

This question is harder than it looks. The best path does not have to start at the root. It does not have to end at a leaf. It can go up from one node, turn at a top node, and come down into another branch. Many beginners try a simple method first, and that method gives the wrong answer as soon as the tree has negative numbers.

The method in this lesson handles both positive and negative values. It uses one idea that comes up again in later tree lessons: each node sends one number up to its parent, and the parent decides what to do with it. The lesson uses recursion, which means a function that calls itself on smaller parts of the tree. If recursion is new to you, read the recursion module first.

The problem in plain words

Look at this tree:

        -10
        /  \
       9    20
           /  \
          15    7

The path 15, 20, 7 goes from one leaf up to 20 and down to another leaf. Its sum is 15 + 20 + 7, which is 42. No other path is bigger. The path 9, -10, 20, 15 has sum 34, because the -10 at the top pulls the total down.

The answer is 42. The path does not include the root, which holds -10. It bends at the node 20. That bend is the key detail. A path can go up and then down, so it has a top node where it turns. The best path through a tree is the best path that bends at some node.

Two words need a definition before we go on.

• A path is a sequence of nodes where each node is directly joined to the next one. A path may have one node.
• A gain is the best sum you can collect when you start at a node and walk down into at most one of its children, then stop. It is the value you hand up to the parent.

Start with one node

Take the smallest case. A tree with one node holding the value 5. The only path is the node itself, so the answer is 5. A tree with one node holding -7 has the answer -7. A path must have at least one node, so the answer is never empty. This is a rule you must keep in your code. If you start with 0 as the answer, you will wrongly return 0 for an all-negative tree.

Now take a node with two children, holding 1, 2 and 3:

    1
   / \
  2   3

There are three useful paths here. The path 2, 1, 3 has sum 6. The path 1, 2 has sum 3. The path 1, 3 has sum 4. The best is 2, 1, 3, which bends at the root.

So at node 1, we need to add the values of both children. The path 2, 1, 3 goes through both sides. The path that goes up from node 1 to its parent cannot use both sides, because a path that leaves a node going up has only one way down below it.

This gives the main rule of the lesson. A node can do two things with its children.

1. It can bend. The path uses both children, and it stops here. This path is a candidate for the answer, but it cannot be extended upward.
2. It can pass one side up. The path uses at most one child, and it continues to the parent.

The idea: the gain a node can pass up

For each node, compute the gain from its left child and the gain from its right child. Call them left and right. Then the best path that bends at this node is:

node value + left + right

Then the node sends one value up to its parent. That value is the node value plus the larger of the two gains:

node value + max(left, right)

If the path continues upward, it can use only one side below the node, because a straight path cannot fork. You can see this in the tree above. Node 20 sends 20 + 15 = 35 up to -10. It does not send 20 + 15 + 7, because the path 15, 20, 7 would then be joined to -10 and that is not a path.

Clipping: drop a branch that hurts

Some gains are negative. Suppose a child has a gain of -4. If you add that child into a path, the sum goes down by 4. You are better off leaving that child out.

To leave a child out, you clip its gain at zero. Clipping means replacing a negative value with zero. The rule for each child is:

use = max(0, gain of child)

If the gain is negative, use is 0, and the path does not go into that child. If the gain is positive, the path goes in and collects that value.

Here is the same tree with a negative branch:

    5
   / \
 -4   6

The node -4 has no children, so its gain is -4. At the node 5, clipping turns that -4 into 0. So the bent path at 5 is 5 + 0 + 6 = 11. The path 6, 5 has sum 11, and that is the answer. Without clipping, the code would add -4 and get 5 + (-4) + 6 = 7, which is wrong.

Clipping uses the rule "do not join a branch that lowers the sum". It does not remove the node itself. Only the child's contribution is clipped. The node value is always included in a path that goes through the node.

Example 1: the tree from the start

Here is the tree again:

        -10
        /  \
       9    20
           /  \
          15    7

Walk up from the bottom. Each step uses the two values described above.

• Node 9 has no children. Its gain is 9. Its bent path is 9.
• Node 15 has no children. Its gain is 15.
• Node 7 has no children. Its gain is 7.
• Node 20 has children 15 and 7. Both are positive, so they are kept. The bent path is 20 + 15 + 7 = 42. This is the best so far. The gain sent up is 20 + max(15, 7) = 35.
• Node -10 has children 9 and 20. The clipped left is 9, and the clipped right is 35. The bent path is -10 + 9 + 35 = 34. This is not better than 42. The gain sent up is not needed, because -10 is the root.

The answer is 42.

Example 2: every value is negative

Now take a tree where every value is negative:

      -3
     /  \
   -1    -2

The rule says a path must have at least one node. The best single node is -1. Check the other paths: -3 alone is -3. The path -1, -3 has sum -4. The path -3, -2 has sum -5. The path -1, -3, -2 has sum -6. So the answer is -1.

Walk up the tree.

• Node -1 has no children. Its gain is -1. Its bent path is -1, which is the best so far.
• Node -2 has no children. Its gain is -2. Its bent path is -2. Nothing changes.
• Node -3 has children -1 and -2. Both gains are negative, so both clip to 0. The bent path is -3 + 0 + 0 = -3. This is not better than -1. The gain sent up is -3.

The answer is -1, which is the largest single node. This is why the first best value must be the node value and not zero. Clipping only decides whether a child joins a path. It never removes the node that the path is built on.

Example 3: a path that bends at a middle node

This tree has a negative node in the middle with a good value below it:

        5
       / \
     -2    6
     / \
    9   -4

Walk up.

• Node 9 has no children. Its gain is 9.
• Node -4 has no children. Its gain is -4. It clips to 0 when it is used.
• Node -2 has children 9 and -4. The clipped left is 9, and the clipped right is 0. The bent path is -2 + 9 + 0 = 7. The gain sent up is -2 + max(9, 0) = 7.
• Node 6 has no children. Its gain is 6.
• Node 5 has children -2 and 6. The clipped left is 7, and the clipped right is 6. The bent path is 5 + 7 + 6 = 18. The path 9, -2, 5, 6 has sum 18.

The answer is 18. The node -2 is kept, because the path through it is still good: the 9 below it is larger than the cost of the -2.

The C++ code

The tree is built from nodes. Each node has an integer value and two owning pointers, one to each child. In this course, std::unique_ptr is a pointer that owns the node it points to. When the owner goes away, the node is freed. You do not have to write delete.

The function gain does the work. It returns the gain for a node, and it updates best for the bent path at that node. The function maxPathSum starts best at the smallest long long value and calls gain on the root.

#include <algorithm>
#include <iostream>
#include <limits>
#include <memory>
 
struct Node {
    int val;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : val(v) {}
};
 
std::unique_ptr<Node> make(int v, std::unique_ptr<Node> l = nullptr, std::unique_ptr<Node> r = nullptr) {
    auto n = std::make_unique<Node>(v);
    n->left = std::move(l);
    n->right = std::move(r);
    return n;
}
 
// Returns the best path that starts at n and goes down one side only.
// Records in best the best path that bends at n (uses both sides).
long long gain(const Node* n, long long& best) {
    if (n == nullptr) return 0;
    long long left = std::max(0LL, gain(n->left.get(), best));
    long long right = std::max(0LL, gain(n->right.get(), best));
    best = std::max(best, n->val + left + right);
    return n->val + std::max(left, right);
}
 
long long maxPathSum(const Node* root) {
    long long best = std::numeric_limits<long long>::min();
    gain(root, best);
    return best;
}
 
int main() {
    // Example 1: the best path is 15 -> 20 -> 7.
    auto t1 = make(-10,
                   make(9),
                   make(20, make(15), make(7)));
    std::cout << "example 1: " << maxPathSum(t1.get()) << '\n';
 
    // Example 2: the best path is 2 -> 1 -> 3.
    auto t2 = make(1, make(2), make(3));
    std::cout << "example 2: " << maxPathSum(t2.get()) << '\n';
 
    // Example 3: every value is negative, so the answer is the largest single node.
    auto t3 = make(-3, make(-1), make(-2));
    std::cout << "example 3: " << maxPathSum(t3.get()) << '\n';
 
    // Example 4: the best path is 3 -> 1 -> 0 -> 4, which has sum 8.
    // The path 2 -> 1 -> 3 has sum 6, and it is not the best.
    auto t4 = make(0, make(1, make(2), make(3)), make(4));
    std::cout << "example 4: " << maxPathSum(t4.get()) << '\n';
 
    // Example 5: a single negative node.
    auto t5 = make(-7);
    std::cout << "example 5: " << maxPathSum(t5.get()) << '\n';
 
    // Example 6: a negative middle node with a big positive subtree below it.
    // Shape: root 5, left child -2 (children 9 and -4), right child 6.
    auto t6 = make(5, make(-2, make(9), make(-4)), make(6));
    std::cout << "example 6: " << maxPathSum(t6.get()) << '\n';
    return 0;
}

Two details are worth noticing.

The variable best is passed by reference. This is how gain reports the bent path at each node back to maxPathSum. The function return value is used for the parent, and best is used for the answer. Keep these two jobs separate in your head. The return value goes up. The best value goes to the top.

The line best = std::max(best, n->val + left + right); runs for every real node, including nodes that have one child or none. A missing child has gain 0 after clipping, so it adds nothing. That is why a leaf gets its own value as its bent path.

Running it

Compile with these flags and run the program.

g++ -std=c++20 -Wall -o path13 path13.cpp
./path13

The output is:

example 1: 42
example 2: 6
example 3: -1
example 4: 8
example 5: -7
example 6: 18

Each line matches the hand work above. Example 1 gives 42, example 3 gives -1, and example 6 gives 18.

Common mistakes

Returning both sides to the parent

The most common bug is to send the full bent sum up instead of the one-sided gain. The line that returns to the parent becomes return n->val + left + right;. The code then compiles and runs, but the answer can be too large.

Take this tree. The root is 0. Its left child is 1, which has children 2 and 3. Its right child is 4.

        0
       / \
      1   4
     / \
    2   3

The correct best path is 3, 1, 0, 4, with sum 8. A path is a single line, so it cannot go from 2 to 1 to 3 and also continue up to 0. Going up from 1 means leaving 1 through one side only.

The buggy version returns 1 + 2 + 3 = 6 from node 1 to the root. At the root, the bent sum is then 0 + 6 + 4 = 10. The program prints 10. That number is not a path.

Here is the output from the version with the bug, on the same tree:

example 4: 10

The fix is to return n->val + std::max(left, right), which sends only one side up.

Forgetting to clip

If you leave out the clipping, a negative branch is added into the path. Here the code uses gain(n->right.get(), best) directly, with no std::max(0LL, ...).

Take the tree with 5 at the root, -4 on the left and 6 on the right. The correct answer is 11, from the path 6, 5. The buggy version adds the -4, so the bent sum at 5 is 5 - 4 + 6 = 7. The program then prints the wrong answer:

7

The fix is to clip each child's gain at zero before using it. The value 11 comes from clipping -4 to 0.

Starting the best value at zero

Some people start best at 0 because it looks like a neutral start. This fails when every value is negative. For example 3, the answer is -1. If best starts at 0, the program returns 0, which is not the sum of any path in that tree.

With best starting at 0, a tree whose root is -3 with children -1 and -2 prints 0. Start best at the smallest possible value, as the code does with std::numeric_limits<long long>::min(). Then the first real node sets it to its own value.

A compile error with unique_ptr

The tree stores each child in a std::unique_ptr, and a unique_ptr cannot be copied. If you write a copy by mistake, the compiler stops with an error. Here is a short program that makes this mistake:

#include <memory>
struct Node { int val; std::unique_ptr<Node> left; explicit Node(int v) : val(v) {} };
int main() {
    auto root = std::make_unique<Node>(1);
    root->left = std::make_unique<Node>(2);
    std::unique_ptr<Node> copy = root->left;
    return copy->val;
}

The compiler output, with the first part of the message:

err13.cpp: In function 'int main()':
err13.cpp:6:40: error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = Node; _Dp = std::default_delete<Node>]'
    6 |     std::unique_ptr<Node> copy = root->left;
      |                                        ^~~~

The message says that the copy constructor is deleted. The pointer owns the node, so two owners would both try to free it. The fix is to use a plain pointer to look at the node, with root->left.get(), or to use std::move if you want to take ownership.

Inside gain, the code only reads the children with .get(), so it never copies a unique_ptr.

Practice

Each exercise has its answer below it. Try the exercise first, then check your answer.

Exercise 1: trace the tree by hand

Find the maximum path sum of this tree. Walk up from the bottom and write the gain at each node.

      4
     / \
   -1    2
   /
  3

Show the answer

The node 3 has no children, so its gain is 3. The node -1 has one child with gain 3 and no right child. Its bent path is -1 + 3 + 0 = 2, and its gain sent up is 2. The node 2 is a leaf with gain 2. The root 4 has clipped left 2 and clipped right 2. Its bent path is 4 + 2 + 2 = 8. The path is 3, -1, 4, 2, with sum 8. The answer is 8.

Exercise 2: a root with one negative child

Find the maximum path sum of a tree with root -2 and only one child, -3.

Show the answer

The answer is -2. The child -3 has gain -3, which clips to 0 at the root. The bent path at -2 is -2 alone, and no path with -3 in it is better. The path must have at least one node, so the best is the root by itself.

Exercise 3: the best path that must contain the root

Write a function throughRoot that returns the best path sum over all paths that contain the root. Use the gain function from the lesson. Test it on the tree from Example 1, where the root is -10, with 9 on the left and 20 on the right, and 20 has children 15 and 7.

Show the answer

long long throughRoot(const Node* root) {
    if (root == nullptr) return 0;
    long long dummy = std::numeric_limits<long long>::min();
    long long l = std::max(0LL, gain(root->left.get(), dummy));
    long long r = std::max(0LL, gain(root->right.get(), dummy));
    return root->val + l + r;
}

The dummy value is needed because gain requires a best argument, but this function does not need the best value across the whole tree. On Example 1, the result is -10 + 9 + 35 = 34. The path 9, -10, 20, 15 has sum 34.

Exercise 4: why not return the sum of both sides?

Explain in your own words why n->val + left + right cannot be sent to the parent.

Show the answer

A path that goes up through a node can use only one child of that node, because the path is a single line. If the node sends up both children, the parent adds two branches that no single line can cover. The sum then counts nodes that are not on any one path. In the tree from the mistakes section, the bug gives 10, but the real best path has sum 8.

Exercise 5: count the calls

A tree has n real nodes. How many calls does gain make, including the calls that receive a null child?

Show the answer

There are 2n child slots in total, because each node has two. Every real node except the root fills one slot. So n - 1 slots are filled, and n + 1 slots are empty. Each real node gets one call, and each empty slot gets one call that returns 0. The total is n + (n + 1), which is 2n + 1. For the 5-node tree in Example 1, that is 11 calls.

Summary

• A path can bend at a top node, so the best path does not have to include the root.
• Each node sends one side of its best path up to its parent, which is its value plus the larger clipped child gain.
• Each node also checks the bent path, which is its value plus both clipped child gains.
• Clipping a child's gain at zero drops a branch that would lower the sum.
• The best value must start at the smallest possible number, so an all-negative tree returns its largest single node.