Maximum path sum with negative values in Python

Why this matters

A path sum problem asks for the largest total along a route through a tree. Think of a tree of rooms in a building, where each room has a score that can be positive or negative. You want the route, between any two rooms, with the highest total score. The route does not have to start at the top room, and it does not have to end at a leaf.

This is a common interview question. The first idea, trying every possible route, is slow for a large tree. The fix is a useful habit: each node passes one number up to its parent, and that number carries exactly the information the parent needs. Once you see that habit, many tree problems become short.

The any-path sums lesson earlier in this module counts paths that add up to an exact target. Here the goal is the largest total, and some values are negative, so a branch that looks promising can drag the total down. The code has to skip those branches.

Words you will need

• Node: one box in the tree. It holds a number and points to up to two children.
• Root: the top node of the tree. It has no parent.
• Leaf: a node with no children.
• Subtree: a node together with everything below it.
• Path: a list of nodes where each node is linked to the next by a parent and child link. A path may go down, or go up once and then go down. It never visits a node twice.
• Top of a path: the node on the path that is closest to the root. Every path has exactly one top. From the top, the path goes down into at most two children, one on the left and one on the right.
• Gain: in this lesson, the best total you can collect starting at a node and going down into at most one of its children. A gain is what a node hands up to its parent.
• Clip: replace a negative number with 0. Clipping a child's gain means "if it hurts, do not take it".
• Nonlocal variable: a variable that belongs to the function around a nested function. The nested function declares it with nonlocal, so every call reads and writes the same variable. The code below uses one to hold the best answer found so far.
• float("-inf"): a number smaller than every whole number. It is a safe starting value for a "biggest so far" search, because the first real candidate always beats it.
• max(a, b): returns the larger of two numbers.

The problem, with a first example

Here is a small tree with a negative root.

      -10
      /  \
     9    20
          /  \
         15    7

Some paths and their totals:

• Just the node 9: 9.
• Just the node 15: 15.
• The path 15, 20, 7: 15 + 20 + 7 = 42.
• The path -10, 9: -10 + 9 = -1.
• The path -10 alone: -10.

The best is 42. The path has its top at 20. It does not include the root, and it does not start at the root. A path can bend at its top, so the answer is not always a straight line down from the root.

The top node matters because it is the only place where a path can use both of its children. Every other node on the path has the path arriving from one side and leaving by the other.

The idea, built up step by step

Two separate questions come up for every node.

First question: if this node is the top of a path, what is the best total? The path can use both children, so the total is the node's value plus what the left child can offer plus what the right child can offer. A child can offer nothing, so each offer is clipped at 0. If a child's offer is negative, the path simply does not go into that child.

Second question: what can this node offer its parent? A parent can use only one side of this node. A path that goes through this node and both of its children cannot continue upward, because it would turn back on itself. So the node offers its value plus the better of its two clipped child offers.

This gives the full rule. For each node:

1. Ask the left child for its offer. Clip it at 0.
2. Ask the right child for its offer. Clip it at 0.
3. Make a candidate: node value + left offer + right offer. If the candidate beats the best seen so far, record it.
4. Return to the parent: node value + the larger of the two clipped offers.

Step 3 covers the case where this node is the top. Step 4 covers the case where the path continues upward. Since step 3 runs at every node, the best candidate found anywhere in the tree is the answer.

An empty child (None) gives an offer of 0. There is nothing to add, and nothing to clip.

Why clip? A child's offer is useful only when it is positive. If the left subtree gives back -5, the parent is better off without it, because adding -5 can only lower the total. Clipping at 0 means the parent quietly skips that branch.

Clipping does not apply to the node's own value. A node with value -4 still counts when its children are worth a lot. Example 5 below shows this.

Worked example 1: a tree with positive values

The tree has root 1, with children 2 and 3.

    1
   / \
  2   3

The code visits nodes in the order they finish, which is 2, then 3, then 1. Each row shows what happens at that node.

The answer is 6, the path 2, 1, 3. The node 1 returned 4 because a path going upward can use only the larger side. It returned 4 and not 6 because 6 would turn back at node 1.

Worked example 2: the tree with -10 at the root

Now the tree from the first example. The finish order is 9, 15, 7, 20, -10.

The node 20 is the top of the best path, with candidate 42. The root's candidate is 34, which is lower, so the best stays at 42. The root's own value of -10 pulled its candidate down, which is why the root is not the top of the best path.

The answer is 42.

The code

The function below holds the rule. The inner function gain returns the offer for the parent and updates the best candidate. The variable best belongs to max_path_sum, and gain changes it with nonlocal. The file ends with five examples.

Save the code as max_path.py and run python3 max_path.py.

The output is:

Example 1: 6
Example 2: 42
Example 3: -1
Example 4: 2
Example 5: 11

Each line matches a hand trace. Example 1 is worked above, and example 2 is the table above. The next three examples cover the cases the first two do not.

Example 3: every value is negative

The tree has root -3 with children -2 and -1. Every path has a negative total, so the best answer is the least negative single node. A path must contain at least one node, so the empty path is not allowed.

• Node -2: both children empty, candidate -2, best -2, returns -2.
• Node -1: candidate -1, best -1, returns -1.
• Node -3: clipped offers 0 and 0, candidate -3, best stays -1, returns -3.

The answer is -1.

This example is why best starts at float("-inf") and not at 0. Starting at 0 would wrongly allow the empty path. The mistakes section shows the wrong result.

Example 4: drop a negative child

The tree has root 2 with children -5 and -1.

• Node -5: candidate -5, best -5, returns -5.
• Node -1: candidate -1, best -1, returns -1.
• Node 2: both offers are negative, so both clip to 0. Candidate 2 + 0 + 0 = 2. Best becomes 2. Returns 2.

The answer is 2, the root alone. Without clipping, the root's candidate would be 2 + (-5) + (-1) = -4, and the root's own value would never be considered as a path by itself. That is mistake 1 below.

Example 5: a negative middle node with two useful children

The tree has root 5, whose only child is -4. The node -4 has children 10 and 3.

• Node 10: candidate 10, best 10, returns 10.
• Node 3: candidate 3, best 10, returns 3.
• Node -4: clipped offers 10 and 3. Candidate -4 + 10 + 3 = 9. Best stays 10. Returns -4 + 10 = 6.
• Node 5: clipped offers 6 and 0 (no right child). Candidate 5 + 6 + 0 = 11. Best 11. Returns 11.

The answer is 11, the path 10, -4, 5. The node -4 is negative, but its left child is worth 10, so its offer of 6 is positive and it stays in the path. Clipping works on the offer from the child, not on the node's own value.

Common mistakes

Mistake 1: forgetting to clip the offers

Here is a version of gain with the clipping removed. It is the same function as above, with max(0, ...) taken out of the two child lines.

The output is:

Example 4 without clipping: -1

The root's candidate becomes 2 + (-5) + (-1) = -4. The root alone, which is the right answer, is never recorded, so the best it finds is the single node -1. The fix is the two lines with max(0, ...).

Mistake 2: starting best at 0

If best starts at 0, the code acts as if the empty path were allowed. On example 3 it prints 0 instead of -1. Start at float("-inf") instead, and let the first real candidate set the value.

Mistake 3: no check for None at the top of gain

Without the None check, the function keeps calling itself on empty children and then tries to read an attribute from None. Python stops the program with this output, from a version that has no check.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
 
def gain_no_null_check(node):
    left = max(0, gain_no_null_check(node.left))
    right = max(0, gain_no_null_check(node.right))
    return node.val + max(left, right)
 
 
gain_no_null_check(TreeNode(2, TreeNode(-5), TreeNode(-1)))

The output is:

Traceback (most recent call last):
  File "main.py", line 14, in <module>
    gain_no_null_check(TreeNode(2, TreeNode(-5), TreeNode(-1)))
    ~~~~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 9, in gain_no_null_check
    left = max(0, gain_no_null_check(node.left))
                  ~~~~~~~~~~~~~~~~~~^^^^^^^^^^^
  File "main.py", line 9, in gain_no_null_check
    left = max(0, gain_no_null_check(node.left))
                  ~~~~~~~~~~~~~~~~~~^^^^^^^^^^^
  File "main.py", line 9, in gain_no_null_check
    left = max(0, gain_no_null_check(node.left))
                                     ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'left'

The message says that the attribute left was read from a value that is None. The caret lines under each frame can differ by Python version. The repeated lines show the function calling itself on an empty child. The fix is the if node is None check at the start of the function.

Mistake 4: returning both sides to the parent

A common error is to return the whole candidate, both sides included, to the parent. The parent then treats a path that turns back at the child as if it were a straight path.

The output is:

both sides returned: 22

Take the tree with root 1, whose left child is another 1, and that child has two leaves 10 and 10. The correct answer is 21, the path 10, 1, 10. The version above prints 22 for this tree. The 22 comes from adding the root to the walk 10, 1, 10. The middle node is then used twice: once between its two leaves, and again on the way up to the root. That is not a path.

Practice

Exercise 1. The tree has root 1, with left child -2 and right child 3. What does max_path_sum return?

Show the answer

It returns 4. The path 1, 3 has total 4. The node -2 gives an offer of -2, which clips to 0, so the parent skips it.

Exercise 2. The tree is a single node with value -5. What does max_path_sum return?

Show the answer

It returns -5. The only path is the node itself. A path must have at least one node, so the empty path is not allowed.

Exercise 3. The tree has root 10. Its left child is -2, which has a left child 3 and a right child -4. Its right child is 5. What does max_path_sum return? Name the path.

Show the answer

It returns 16. The node -4 clips to 0, so -2 has clipped offers 3 and 0. Its candidate is -2 + 3 + 0 = 1, and it returns -2 + 3 = 1 to the root. The root's candidate is 10 + 1 + 5 = 16. The path is 3, -2, 10, 5.

Exercise 4. Why does gain return only one side to its parent, and not both?

Show the answer

A path that goes up from a node cannot also go down both children. If it did, it would meet itself at the node. So the parent can use the node's value plus one of its two sides. The other side can only be used when this node is the top of the path, which is why the candidate has both sides and the return value has one.

Exercise 5. The tree has root 6. Its left child is -8, which has a left child 4 and a right child 9. The root has no right child. What does max_path_sum return?

Show the answer

It returns 9. The node -8 has offers 4 and 9. Its candidate is -8 + 4 + 9 = 5, and it returns -8 + 9 = 1. The root's left offer is 1, so its candidate is 6 + 1 = 7. The best single candidate is the node 9 alone, which is 9.

Summary

• Each node returns one side to its parent: its value plus the larger clipped child offer.
• Each node also records a candidate that bends at it: its value plus both clipped child offers.
• Clipping a child's offer at 0 makes a negative branch disappear from the path.
• best starts at float("-inf"), so an all-negative tree returns the least negative single node.
• The None check at the start of gain is what stops the recursion at empty children.