Root-to-leaf and any-path sums in Python

Why this matters

Many questions about a tree are questions about a path. A route on a map is a path from a start point to an end point. A folder inside another folder, with file sizes added up along the way, is a path. A decision tree in a game or a loan approval flow gives a path for each outcome. A common task is to ask whether some path adds up to a target number, such as a budget, a cost limit or a score.

This lesson covers two versions of the question. The first asks for paths that start at the root and end at a leaf. The second asks for paths that go downward and can start at any node. The second version is harder, because a naive search checks every start node, and that repeats work. The running-sum method in this lesson counts all of them in one walk over the tree.

The lesson assumes you know binary trees, nodes, leaves and recursion. The words are defined below.

Words you will need

• Binary tree: a tree where each node has at most two children, called left and right.
• Root: the top node of the tree.
• Leaf: a node with no children.
• Path: a list of nodes where each node is the child of the one before it. A root-to-leaf path starts at the root and ends at a leaf.
• Downward path: a path that moves only from a parent to a child. It can start at any node, and it can stop at any node below the start. It does not have to reach a leaf.
• Sum: the total of the values on a path.
• Target: the number the sum must equal.
• Running sum or prefix sum: the total of the values from the root down to the current node. The running sum at a node is the sum of the path from the root to that node.
• Dictionary: a table that stores key and value pairs and finds a key in about one step. The method dict.get(key, default) returns the default when the key is missing.
• Backtracking: when a recursive walk adds something to a shared list, goes deeper, and then takes it back out before it returns. It lets one list serve every path.
• Recursion: a function that calls itself on a smaller part of the problem, until it reaches a case that needs no more calls.

Part 1: root-to-leaf paths

The question

Given a tree and a target, is there a path from the root to a leaf whose values add up to the target?

Take a small tree. The root holds 1, and it has one child, a leaf holding 2.

    1
   /
  2

The only root-to-leaf path is 1, 2. Its sum is 3. So the answer is yes for target 3 and no for target 1.

A recursive check

The idea is to walk down from the root and keep track of what is still left to reach the target. At the root, the remaining amount is the target. At each node, you take the node's value away from the remaining amount, and pass the new remaining amount to the children. When you reach a leaf, the path is complete. The answer is yes if the remaining amount is exactly 0 at that leaf.

Here is the walk for target 3 on the small tree.

1. Start at node 1 with remaining 3. Subtract 1, so the remaining amount is 2. Node 1 is not a leaf, so go to its children.
2. The left child is node 2 with remaining 2. Subtract 2, so the remaining amount is 0. Node 2 is a leaf.
3. The remaining amount is 0 at a leaf, so the answer is yes.

Code for this check is short:

def has_path_sum(node, remaining):
    if node is None:
        return False
    left = remaining - node.val
    if node.left is None and node.right is None:
        return left == 0
    return has_path_sum(node.left, left) or has_path_sum(node.right, left)

The or in the last line stops as soon as one side returns True. If the left child finds a matching path, the right child is not searched.

Python integers have no fixed size limit, so the sums can grow as large as the values allow. A language with fixed-size integers needs a wider type for long sums, but Python does not.

Two details matter. A None node returns False, because there is no path through a missing child. A node counts as a leaf only when both of its children are None. A node with one child is not a leaf, and the check must go on down the child that exists.

Collecting the paths themselves

Sometimes you need the paths, not only a yes or no. The function keeps one shared list of the values on the current path. It adds the node's value when it enters the node, and removes the last value before it leaves. When it reaches a leaf whose sum matches, it stores a copy of the list.

The copy is needed. The shared list keeps changing while the walk continues, so storing the list itself would store a list that is empty or changed by the time you read the result. Storing a copy keeps the path as it was at the leaf. The function list(path) makes that copy.

def collect_paths(node, target, sum_so_far, path, out):
    if node is None:
        return
    path.append(node.val)
    sum_so_far += node.val
    if node.left is None and node.right is None:
        if sum_so_far == target:
            out.append(list(path))
    else:
        collect_paths(node.left, target, sum_so_far, path, out)
        collect_paths(node.right, target, sum_so_far, path, out)
    path.pop()

The line path.pop() removes the last item of the list. Each call that adds a value ends with path.pop(), so the list holds the same values when that call returns as when it started.

A worked example

Here is a tree with two root-to-leaf paths that sum to 22.

             5
           /   \
          4     8
         /     / \
       11    13   4
      /  \         / \
     7    2       5   1

The root-to-leaf paths are 5, 4, 11, 7 (sum 27), 5, 4, 11, 2 (sum 22), 5, 8, 13 (sum 26), 5, 8, 4, 5 (sum 22), and 5, 8, 4, 1 (sum 18). Two of them sum to 22.

The program in Part 2 prints that result. The code for the whole program is shown in full in the code section of Part 2, so the same file runs both parts.

Run the check with the target 22 and the target 26 on the same tree. The first gives the two paths that sum to 22. The second gives 5, 8, 13, which sums to 26.

The program output

These are the real results of the program. The full listing is in the code section below.

example 1 hasPathSum(22): True
example 1 paths summing to 22: [[5, 4, 11, 2], [5, 8, 4, 5]]
example 1 paths summing to 26: [[5, 8, 13]]
example 1 hasPathSum(100): False

Part 2: any-path sums

The question

Now the path can start at any node, and it can stop at any node below the start. Only downward moves are allowed. How many such paths add up to the target?

Take the second example tree from the code section below, with the target 8. The answer is the number of downward paths whose sum is 8. The count is what matters here, and the method below gets it without listing every path.

The slow way

The simple method is to try every node as a start and walk down from it, adding values until you reach a leaf. Each walk adds one count for each time its sum equals the target. For a tree with n nodes, the walks can cover up to about n squared steps in a bad shape, such as a long chain.

The slow method is correct, and the program uses it as a check. But the same work is repeated. Two starts that share a path below them walk the same nodes again.

The idea: running sums and a dictionary

Use the running sum from the root. Call the running sum at a node S. Think about a downward path that starts just below some ancestor A and ends at the current node C. Its sum is the running sum at C minus the running sum at A. So if the path sums to the target k, then:

runningSum(C) - runningSum(A) = k

Rearranged, that means runningSum(A) = runningSum(C) - k. So at node C, the number of valid starting points is the number of ancestors whose running sum equals runningSum(C) - k.

The function keeps a dictionary. The dictionary stores how many times each running sum has appeared on the path from the root to the current node. At each node, it looks up runningSum(C) - k in the dictionary. The value it finds is the count of valid paths that end at C. Then it adds runningSum(C) to the dictionary, goes into the children, and takes it out again on the way back.

The dictionary starts with the entry 0 with count 1. This stands for the empty path before the root. When a node's running sum equals the target, the lookup finds 0, and that counts the path from the root down to the node.

A worked trace

Take a chain of three nodes with values 1, 2 and 3, going right, and the target 3. The valid paths are 1, 2 (sum 3) and 3 (sum 3). The answer is 2.

The program below prints a line at each node, with the running sum and the dictionary before the node is added. Run it on the chain 1, 2, 3 with target 3. The real output is:

node 1: running sum 1, looking for -2, map before = {0: 1}
node 2: running sum 3, looking for 0, map before = {0: 1, 1: 1}
node 3: running sum 6, looking for 3, map before = {0: 1, 1: 1, 3: 1}
total = 2

Read the first line. At node 1 the running sum is 1. The code looks for 1 minus 3, which is -2. The dictionary has only 0, so the count adds nothing.

Read the second line. At node 2 the running sum is 3. The code looks for 0. The dictionary has 0 with count 1, so the path that starts at the root and ends at node 2 is counted. That is the path 1, 2.

Read the third line. At node 3 the running sum is 6. The code looks for 3. The dictionary has 3 with count 1, which is the running sum at node 2. So the path that starts just below node 2 and ends at node 3 is counted. That is the path 3.

The code

This program holds both parts. It has the root-to-leaf functions from Part 1, the running-sum count, the slow check, and the examples that print the results.

Output:

example 1 hasPathSum(22): True
example 1 paths summing to 22: [[5, 4, 11, 2], [5, 8, 4, 5]]
example 1 paths summing to 26: [[5, 8, 13]]
example 1 hasPathSum(100): False
example 2 any-path sums equal to 8: 3
example 2 brute force for 8: 3
example 2 any-path sums equal to 3: 3
example 2 any-path sums equal to 0: 0
example 3 chain of ones, target 2: 3

The second example tree is the one drawn below. Its values are 10, 5, -3, 3, 2, 3, -2, 1 and 11, and negative values are allowed.

            10
          /     \
         5       -3
       /   \         \
      3     2         11
     / \     \
    3  -2     1

For the target 8 the three downward paths are 5 then 3 (the 3 under 5), 5 then 2 then 1, and -3 then 11. For the target 3 they are the 3 under 5, the 3 under that 3 (a leaf), and 2 then 1. The dictionary method and the brute force method agree on the target 8.

Testing against the slow method

A single example does not prove the method is right. A separate test, which is not listed here, makes random trees, computes the count with the dictionary method and with the slow method, and compares the two. Its trees have values from -3 to 5 and targets from -3 to 3. In a Python test run, the two methods agreed on all 3000 random trees.

Negative values are the reason the test matters. With only positive values, the running sum grows at every step going down, so each running sum appears at most once on a root path. With negative values, the running sum can go down and come back up, so the same running sum can appear more than once on one root path. The dictionary stores a count for each running sum, so it handles that case.

Why the dictionary must be emptied

The dictionary must hold only the running sums of the ancestors of the current node. The code adds the running sum of a node before it goes into the children, and takes it out after both children are done:

prefix_count[running_sum] = prefix_count.get(running_sum, 0) + 1
count += count_from(node.left, running_sum, target, prefix_count)
count += count_from(node.right, running_sum, target, prefix_count)
prefix_count[running_sum] -= 1

Without the last line, the running sums from the left branch would stay in the dictionary when the code walks the right branch. A path could then start in the left branch and end in the right branch. That is not a downward path, and the count would be too high. The subtraction is what keeps the dictionary limited to the current root path. An entry that goes back to 0 counts nothing, so it does no harm.

Common mistakes

Treating a node with one child as a leaf

A leaf has no children at all. A common error checks only one child, or checks the sum at every node. Take this tree, whose root has only a left child.

    1
   /
  2

A check that treats node 1 as a leaf when its remaining amount is 0 gets the wrong answer. Here is that variant, with its output for the target 1. The correct answer is no, because the only root-to-leaf path is 1, 2 with sum 3.

Output:

wrong_leaf(small, 1): True
correct has_path_sum(small, 1): False

Returning True at a missing child

Another common error returns True when a None child is reached with a remaining amount of 0. That counts a path that ends at a node with a missing child, which is not a leaf.

For the same tree with the target 1, this variant returns True, because the missing right child of node 1 is treated as the end of a path with remaining 0:

null_returns_true(small, 1): True

The fix is to return False for a None node. The leaf check does the work of ending a path.

Storing the shared list instead of a copy

If the code adds the list itself to the result, instead of a copy, every stored entry points to the same list. When the walk ends, that list has been emptied by the backtracking steps. A variant that stored the list itself printed this for the target 22:

The output is:

no copy, 22 paths: [[], []]

The fix is list(path), which copies the list at the moment the leaf matches.

Forgetting that the dictionary starts with 0

The entry 0 with count 1 must be in the dictionary before the walk starts. Without it, a path that starts at the root is never counted. For example, in the chain 1, 2, 3 with target 3, the path 1, 2 starts at the root. It is counted only because the lookup for running sum 3 minus 3 finds 0 in the dictionary.

Using int for the sums

Python integers can grow as large as memory allows, so the sums in this lesson cannot overflow. Languages with fixed-size integers, such as Java's int, need a wider type for long paths with large values. Python needs none of that, but the same logic applies to the code you write in other languages.

Removing the dictionary entry too early

Removing the entry before the children are visited makes the children miss the ancestors. The count then drops for paths that start above the current node. The removal must come after both child calls return.

Practice

Exercise 1. The tree has a root 4, with a left child 2 and a right child 6. Both children are leaves. Which root-to-leaf paths sum to 10?

Show the answer

The two root-to-leaf paths are 4, 2 (sum 6) and 4, 6 (sum 10). Only 4, 6 sums to 10, so the answer is the path [4, 6].

Exercise 2. The tree is a chain of three nodes going left: the root holds 1, its left child holds 2, and that node's left child holds 3. How many downward paths sum to 3?

Show the answer

The downward paths are 1 (sum 1), 1, 2 (sum 3), 1, 2, 3 (sum 6), 2 (sum 2), 2, 3 (sum 5), and 3 (sum 3). Two of them sum to 3: the path 1, 2 and the single node 3. The answer is 2.

Exercise 3. Take the chain 1, 2, 3 going right, and the target 5. Which downward paths sum to 5, and what does the running-sum method count at node 3?

Show the answer

The downward paths are 1 (1), 1, 2 (3), 1, 2, 3 (6), 2 (2), 2, 3 (5), and 3 (3). Only 2, 3 sums to 5. At node 3 the running sum is 6, and the function looks for 6 minus 5, which is 1. The dictionary has 1 with count 1, from node 1, so the function counts the path that starts just below node 1 and ends at node 3, which is 2, 3. The count at node 3 is 1.

Exercise 4. Why is the entry 0 with count 1 put in the dictionary before the walk starts?

Show the answer

The entry stands for the empty path above the root. When the running sum at a node equals the target, the lookup for running sum minus target finds 0, which counts the path from the root down to that node. Without the entry, every path that starts at the root would be missed.

Exercise 5. A tree has the values 2, -2 and 2 going down a right chain, and the target is 2. Use the running-sum method to count the paths. Write the running sum at each node.

Show the answer

The running sums are 2 at the first node, 0 at the second, and 2 at the third. The dictionary starts with 0 with count 1. At the first node the running sum is 2, and the function looks for 0, which is in the dictionary, so it counts 1 (the path 2). The dictionary then gets 2 with count 1. At the second node the running sum is 0, and the function looks for -2, which is not in the dictionary, so it counts nothing. The dictionary then gets 0 with count 2. At the third node the running sum is 2, and the function looks for 0, which has count 2, so it counts 2. The total is 3: the path 2 at the first node, the path 2, -2, 2 (sum 2), and the path 2 at the third node alone. The answer is 3. Check it with the slow method on this tree before you trust the count.

Summary

• For a path from the root to a leaf, walk down while subtracting each node's value from the remaining amount, and answer yes when a leaf is reached with 0 left.
• A node is a leaf only when both of its children are missing, and a missing child returns False, not True.
• To collect the paths, add the node to a shared list on the way down, copy the list at a matching leaf, and remove the last item on the way back up.
• For a downward path that can start anywhere, count the earlier running sums that equal the current running sum minus the target, using a dictionary.
• Add each running sum to the dictionary before visiting the children, take it out after, and start the dictionary with the entry 0 with count 1.