Root-to-leaf and any-path sums

Why this matters

Many real questions about trees are about adding values along a route. A folder tree can ask which files under one folder add up to a size limit. A network of connections can ask which routes have a total cost of exactly some amount. In each case, you walk down the tree and keep a total as you go.

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 any path that goes straight down the tree, starting at any node and ending at any node below it. The second version is harder, because the start of the path can be anywhere. A running-sum map solves it without trying every start point one by one.

The next lesson in this module covers the maximum path sum when values can be negative, which asks for the best path rather than a path with an exact sum. This lesson only finds or counts paths with an exact sum.

This lesson assumes you can write a recursive function and that you know what a std::vector and a std::unordered_map do. The nodes are owned through std::unique_ptr, so the tree is freed automatically.

Words used in this lesson

A path in a tree is a list of nodes where each node is a child of the one before it. A path can be a single node. The sum of a path is the total of the values of its nodes.

A root-to-leaf path starts at the root and ends at a leaf. A leaf is a node with no children. An ancestor of a node is any node above it on the way up to the root.

An any-path in this lesson is a downward path. It starts at some node and goes down through children to some node below it. It does not have to start at the root or end at a leaf. It cannot go up to a parent and then down into another branch.

The example tree

Every example in this lesson uses the same tree. It has nine nodes, and some values are negative.

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

The tree has four leaves: the 3 under the left 3, the -2, the 1, and the 11. Reading each root-to-leaf path gives these sums:

Two of the four paths add up to 18. Those two are the answer to the second part of this lesson.

Part 1: is there a root-to-leaf path with this sum?

Start with the yes-or-no version. The idea is to subtract each value from the target as you go down. Call the amount still needed remaining. At the root, remaining is the target. At each node, subtract that node's value. If the node is a leaf, the path is complete, so check whether remaining is exactly 0. If the node is not a leaf, ask the same question of each child.

The recursion does not need to store the path. It only needs the amount still needed.

Here is the function, with a check that a tree with no nodes has no paths:

bool hasRootToLeafSum(const TreeNode* node, int remaining) {
    if (!node) return false;
    remaining -= node->val;
    if (!node->left && !node->right) return remaining == 0;
    return hasRootToLeafSum(node->left.get(), remaining) ||
           hasRootToLeafSum(node->right.get(), remaining);
}

Trace the call for target 18. The table shows the amount still needed after each node is subtracted, along the first branch that the code tries.

Both leaves under the left 3 fail, so the code tries the other child of 5, which is 2. Then it goes to 1. Going down that path, the remaining amount is 8 after 10, 3 after 5, 1 after 2, and 0 after the leaf 1. The leaf passes the check, so the answer is true.

The trace shows the rule. A leaf passes only when the amount needed is exactly used up.

Part 2: list every root-to-leaf path with this sum

A yes-or-no answer is not always enough. You may need to see the paths themselves. Keep a list of the nodes on the current path. When you go down into a node, add its value to the list. When you finish with that node, remove the value again. This is called backtracking: you go down a route, and you come back up to try another route.

Each time a leaf is reached, copy the list if the sum matches. The copy is needed because the list is changed later.

void collectPaths(const TreeNode* node, int target, int sum, std::vector<int>& path,
                  std::vector<std::vector<int>>& out) {
    if (!node) return;
    path.push_back(node->val);
    sum += node->val;
    if (!node->left && !node->right && sum == target) {
        out.push_back(path);
    }
    collectPaths(node->left.get(), target, sum, path, out);
    collectPaths(node->right.get(), target, sum, path, out);
    path.pop_back();
}

The sum argument here adds values going down. It is passed by value, so each call has its own copy. The path list is passed by reference, so every call shares one list. The pop_back at the end removes this node before the caller tries its other child.

Here is what the code does for the example tree with target 18. It pushes 10. It goes to 5, then 3, then the leaf 3. That path sums to 21, so it is not copied. The code then pops back to 3, then tries -2, which is a leaf with sum 16. It pops back up to 5, then goes to 2 and then 1. The sum is 18 at the leaf 1, so [10, 5, 2, 1] is copied. Later the code goes to -3 and then 11, which gives [10, -3, 11].

Part 3: count any-path sums with a running-sum map

Now the harder version. Count every downward path, from any node to any node below it, whose sum equals the target.

A brute force method would start a walk at every node and add values until it reaches the target. That repeats a lot of work. The running-sum method is faster.

The idea

Define the prefix sum of a node as the sum of all values from the root down to that node. It is the running total that the walk has built by the time it reaches the node.

Take a downward path that starts at node a and ends at node b, where a is an ancestor of b or the same node. Its sum is the prefix sum at b minus the prefix sum at the parent of a. The parent of a is the node just above the start of the path. If a is the root, the value above it is the empty start, with prefix sum 0.

Rearrange the same fact. The path from a to b has sum equal to the target if and only if:

the prefix sum at the parent of a equals the prefix sum at b minus the target.

So at each node b, compute the value prefix at b minus target, and count how many ancestors had that prefix sum. Those ancestors are the possible starting points for a path that ends at b. Keep a map from prefix sum to how many times it occurs on the current root-to-node path. Look up the value in the map, and add what you find to the count.

Worked example: target 8

Use the example tree with target 8. Visit the nodes in the order the code does: left branch first, then right branch. Each row shows the prefix sum of the node, the value to look up, and the count found in the map at that moment. The map holds the prefix sums of the current node's ancestors, plus the empty start with sum 0.

The found counts add to 3. The three paths are 5, 3, the path 5, 2, 1, and the path -3, 11. Each one adds to 8, and each one was found at the node where it ends.

Look at the row for node 3 under 5. Its prefix sum is 18. The target is 8, so the look-up value is 10. The root has prefix sum 10 and is an ancestor of this node, so it is in the map. That match means the path starts just below the root, at 5, and ends at 3. The sum is 5 plus 3, which is 8.

Worked example: the empty start

Take a chain of three nodes, 1, 2 and 3, where each node is the right child of the one above. The target is 3. The prefix sums are 1, then 3, then 6.

The count is 2, for the paths [1, 2] and [3]. The row for node 2 finds a match only because of the empty start with prefix sum 0. Without that entry, the path that starts at the root would not be counted.

The code

The map starts with one entry, {0, 1}, which means the empty start has prefix sum 0 and occurs once. The function countAnyPathSums does the work for one node and then calls itself on the children.

int countAnyPathSums(const TreeNode* node, int target, long long runningSum,
                     std::unordered_map<long long, int>& prefixCount) {
    if (!node) return 0;
    runningSum += node->val;
    int count = 0;
    auto found = prefixCount.find(runningSum - target);
    if (found != prefixCount.end()) {
        count += found->second;
    }
    prefixCount[runningSum]++;
    count += countAnyPathSums(node->left.get(), target, runningSum, prefixCount);
    count += countAnyPathSums(node->right.get(), target, runningSum, prefixCount);
    prefixCount[runningSum]--;
    return count;
}
 
int countAnyPathSumsFromRoot(const TreeNode* root, int target) {
    std::unordered_map<long long, int> prefixCount{{0, 1}};
    return countAnyPathSums(root, target, 0, prefixCount);
}

The code adds the current node's prefix sum to the map after the lookup, so a node's own prefix is never matched against itself. The line prefixCount[runningSum]--; at the end is the undo step. It removes the current node's prefix from the map once both children have been handled. Without it, the map would still hold prefix sums from nodes that are not ancestors of the node being visited. The common mistakes section shows what goes wrong.

The runningSum argument is a long long, so that large values do not overflow an int in the running total.

The full program

The program below builds the example tree and runs all three parts. The function make builds a node with two children, and leaf builds a node with none. Both return a std::unique_ptr, so the tree frees itself when main ends.

#include <iostream>
#include <memory>
#include <unordered_map>
#include <vector>
 
struct TreeNode {
    int val;
    std::unique_ptr<TreeNode> left;
    std::unique_ptr<TreeNode> right;
    explicit TreeNode(int v) : val(v) {}
};
 
std::unique_ptr<TreeNode> make(int v, std::unique_ptr<TreeNode> l, std::unique_ptr<TreeNode> r) {
    auto node = std::make_unique<TreeNode>(v);
    node->left = std::move(l);
    node->right = std::move(r);
    return node;
}
 
std::unique_ptr<TreeNode> leaf(int v) {
    return std::make_unique<TreeNode>(v);
}
 
// Part 1: is there a root-to-leaf path with this sum?
bool hasRootToLeafSum(const TreeNode* node, int remaining) {
    if (!node) return false;
    remaining -= node->val;
    if (!node->left && !node->right) return remaining == 0;
    return hasRootToLeafSum(node->left.get(), remaining) ||
           hasRootToLeafSum(node->right.get(), remaining);
}
 
// Part 2: list every root-to-leaf path with this sum.
void collectPaths(const TreeNode* node, int target, int sum, std::vector<int>& path,
                  std::vector<std::vector<int>>& out) {
    if (!node) return;
    path.push_back(node->val);
    sum += node->val;
    if (!node->left && !node->right && sum == target) {
        out.push_back(path);
    }
    collectPaths(node->left.get(), target, sum, path, out);
    collectPaths(node->right.get(), target, sum, path, out);
    path.pop_back();
}
 
// Part 3: count downward paths (any start, any end) with this sum.
// prefixCount maps "sum from the root down to an ancestor" to how many times it
// occurs on the current root-to-node path.
int countAnyPathSums(const TreeNode* node, int target, long long runningSum,
                     std::unordered_map<long long, int>& prefixCount) {
    if (!node) return 0;
    runningSum += node->val;
    int count = 0;
    auto found = prefixCount.find(runningSum - target);
    if (found != prefixCount.end()) {
        count += found->second;
    }
    prefixCount[runningSum]++;
    count += countAnyPathSums(node->left.get(), target, runningSum, prefixCount);
    count += countAnyPathSums(node->right.get(), target, runningSum, prefixCount);
    prefixCount[runningSum]--;
    return count;
}
 
int countAnyPathSumsFromRoot(const TreeNode* root, int target) {
    std::unordered_map<long long, int> prefixCount{{0, 1}};
    return countAnyPathSums(root, target, 0, prefixCount);
}
 
// Same as above but without the {0, 1} starting entry, to show the mistake.
int countWithoutStartEntry(const TreeNode* root, int target) {
    std::unordered_map<long long, int> prefixCount;
    return countAnyPathSums(root, target, 0, prefixCount);
}
 
// Same as above but without undoing the count, to show the second mistake.
int countWithoutUndo(const TreeNode* node, int target, long long runningSum,
                     std::unordered_map<long long, int>& prefixCount) {
    if (!node) return 0;
    runningSum += node->val;
    int count = 0;
    auto found = prefixCount.find(runningSum - target);
    if (found != prefixCount.end()) count += found->second;
    prefixCount[runningSum]++;
    count += countWithoutUndo(node->left.get(), target, runningSum, prefixCount);
    count += countWithoutUndo(node->right.get(), target, runningSum, prefixCount);
    return count;
}
 
void printPath(const std::vector<int>& path) {
    std::cout << "[";
    for (std::size_t i = 0; i < path.size(); ++i) {
        std::cout << path[i] << (i + 1 < path.size() ? ", " : "");
    }
    std::cout << "]\n";
}
 
int main() {
    // 10
    // |- 5
    // |   |- 3
    // |   |   |- 3
    // |   |   `- -2
    // |   `- 2
    // |       `- 1
    // `- -3
    //     `- 11
    auto five = make(5, make(3, leaf(3), leaf(-2)), make(2, nullptr, leaf(1)));
    auto root = make(10, std::move(five), make(-3, nullptr, leaf(11)));
 
    std::cout << "has root-to-leaf sum 18: " << std::boolalpha << hasRootToLeafSum(root.get(), 18) << "\n";
    std::cout << "has root-to-leaf sum 99: " << hasRootToLeafSum(root.get(), 99) << "\n";
 
    std::vector<int> path;
    std::vector<std::vector<int>> paths;
    collectPaths(root.get(), 18, 0, path, paths);
    std::cout << "root-to-leaf paths with sum 18: " << paths.size() << "\n";
    for (const auto& p : paths) printPath(p);
    std::cout << "path left after collecting (should be empty): " << path.size() << "\n";
 
    std::cout << "any-path count for target 8: " << countAnyPathSumsFromRoot(root.get(), 8) << "\n";
    std::cout << "any-path count for target 18: " << countAnyPathSumsFromRoot(root.get(), 18) << "\n";
    std::cout << "mistake, no start entry, target 18: " << countWithoutStartEntry(root.get(), 18) << "\n";
    std::unordered_map<long long, int> bad{{0, 1}};
    std::cout << "mistake, no undo, target 2: " << countWithoutUndo(root.get(), 2, 0, bad) << "\n";
    std::cout << "correct count for target 2: " << countAnyPathSumsFromRoot(root.get(), 2) << "\n";
 
    // A plain chain 1 -> 2 -> 3 (each node is the right child of the one above).
    auto chain = make(1, nullptr, make(2, nullptr, leaf(3)));
    std::cout << "chain 1-2-3, any-path count for target 3: " << countAnyPathSumsFromRoot(chain.get(), 3)
              << " (paths [3] and [1, 2])\n";
    return 0;
}

Compile and run it with:

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

The output, copied from the run on g++ 15.2.0:

has root-to-leaf sum 18: true
has root-to-leaf sum 99: false
root-to-leaf paths with sum 18: 2
[10, 5, 2, 1]
[10, -3, 11]
path left after collecting (should be empty): 0
any-path count for target 8: 3
any-path count for target 18: 3
mistake, no start entry, target 18: 0
mistake, no undo, target 2: 3
correct count for target 2: 1
chain 1-2-3, any-path count for target 3: 2 (paths [3] and [1, 2])

The first lines match the tables above. The mistake lines are explained in the next section. The line that prints the path left after collecting shows 0, which means the backtracking step left the list empty.

Common mistakes

Forgetting the starting entry. The map must begin with {0, 1}. Without it, a path that starts at the root is never counted, because nothing in the map matches a path that begins before the root. Here is the output of the version without the entry, on the example tree with target 18:

mistake, no start entry, target 18: 0

The correct count is 3. All three paths for 18 start at the root: [10, 5, 3], [10, 5, 2, 1] and [10, -3, 11]. Without the starting entry, the program finds none of them.

Forgetting to undo the map. The line prefixCount[runningSum]--; is needed. Without it, a node's prefix sum stays in the map after the walk leaves that node. When the walk later reaches a node in a different branch, the stale entry can match, and the code counts a path that does not exist. Here is the output of the version without the undo step, on the example tree with target 2. The correct answer is 1, which is the single node 2:

mistake, no undo, target 2: 3
correct count for target 2: 1

The extra two counts come from prefix sums of nodes in other branches. They are not ancestors of the node being visited, so those paths are not valid.

Forgetting the pop in part 2. The list of nodes on the path must be removed when the function returns from a node. If path.pop_back() is missing, the list keeps the nodes from earlier branches. The next leaf that matches is copied with those extra values in front, so the printed paths are wrong. The fix is the pop as the last line of the function, after both children have been visited.

Copying a path too late. In part 2 the copy must be made when the leaf is reached, using out.push_back(path). Storing a pointer to path instead of a copy would point at the same list every time, and by the end it would hold whatever was left in it.

Checking the target at every node in part 1. The yes-or-no check in part 1 must happen only at a leaf. A path can end at an inner node, but then it is not a root-to-leaf path. The check remaining == 0 at an inner node would accept a path that is too short.

Confusing the two targets in part 3. The lookup value is runningSum - target, not runningSum + target. A common slip is to add the target. The map then looks for ancestors whose prefix sums are too large, and valid paths are missed.

Using int for the running total. Part 3 stores the running total in a long long. Trees with large values can make the running total larger than an int can hold. The map keys must use the same type as the running total, or the lookups will not match.

Practice

Exercise 1. On the example tree, how many root-to-leaf paths add up to 21?

Show the answer

One. The path is 10, 5, 3, 3, which adds to 21. No other root-to-leaf path adds to 21.

Exercise 2. On the example tree, how many any-path sums equal 11?

Show the answer

Two. The first is the single node 11. The second is the path 5, 3, 3, which adds to 11, going down from the node 5 through its left child 3 to the leaf 3. A run of the same functions with target 11 prints 2.

Exercise 3. Why does the code set the map to {0, 1} before the first call?

Show the answer

It represents the empty start before the root. A path that starts at the root has a starting prefix sum of 0, so the lookup for that path finds this entry. Without it, paths that begin at the root are never counted.

Exercise 4. A tree has one node with value 0. Count the any-path sums that equal 0.

Show the answer

One. The only path is the node itself, which sums to 0. The lookup at the node uses the value 0 minus 0, which is 0, and the empty start with prefix sum 0 is in the map. Running the code on this tree with target 0 prints 1.

Exercise 5. A student changes countAnyPathSums so that it adds the node's prefix sum to the map before the lookup. Does the count change for a tree with a single node with value 0 and target 0?

Show the answer

Yes. Before the lookup, the map now holds the node's own prefix sum, which is also 0. The lookup for 0 minus 0 finds a count of 2, one for the empty start and one for the node itself, so the total becomes 2. The path that is the node by itself is then counted twice. The correct count is 1. The lookup must happen before the current prefix is added.

Summary

• A root-to-leaf sum is checked at the leaf, by subtracting each value from the target on the way down.
• To list paths, push each value onto a list on the way down, copy the list at a matching leaf, and pop the value on the way back.
• For any downward path, the sum from node a down to node b equals the prefix sum at b minus the prefix sum just above a.
• A map from prefix sum to count, with the entry {0, 1} at the start, gives the number of matching paths ending at each node in one walk.
• Undo each prefix sum when leaving its node, so the map only holds ancestors.