Range sum queries in a BST

Why this matters

A range query asks for every value between two limits. A shop might ask for the total of all orders between 20 and 50 dollars. A game might ask for the total score of players whose rank is between 100 and 200. In both cases you want one number back, and you want it without looking at every record.

A binary search tree, or BST, already stores its values in sorted order. That order tells you which parts of the tree can hold values in the range. If a whole subtree is too small or too large, you can skip it. This lesson shows how to use that fact, and how to measure the saving by counting the nodes you visit.

The rule of a BST and the insert code come from the earlier lesson on BST property, insert and search. The code below repeats the insert function so each sample compiles on its own.

The problem in plain words

You have a tree that holds some integers. You are given two numbers, lo and hi. Return the sum of every value v that satisfies lo is at most v and v is at most hi. Both ends are included.

Here is the tree used in most examples. It has nine nodes. The root holds 8.

            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13

For the range from 5 to 13, the values inside the range are 6, 7, 8, 10 and 13. Their sum is 6 + 7 + 8 + 10 + 13, which is 44.

This lesson also counts something called visited nodes. A visit means your code enters a node and looks at it. Each visit costs a small amount of work, so the number of visits is a fair measure of how much work a query does. Two methods can return the same sum and still do very different amounts of work.

Start with the slow method: look at everything

The simplest correct method walks the whole tree. It visits every node, checks whether the value is in the range, and adds it when it is.

Here is the code. The Node type stores a value and two child pointers. A std::unique_ptr is a C++ smart pointer. It owns the node and frees it when the tree is destroyed, so the code has no delete calls.

#include <iostream>
#include <memory>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}
};
 
std::unique_ptr<Node> insert(std::unique_ptr<Node> root, int value) {
    if (!root) return std::make_unique<Node>(value);
    if (value < root->value) root->left = insert(std::move(root->left), value);
    else if (value > root->value) root->right = insert(std::move(root->right), value);
    return root;
}
 
struct Stats {
    long long sum = 0;
    int visited = 0;
};
 
void full_scan(const Node* node, int lo, int hi, Stats& s) {
    if (node == nullptr) return;
    ++s.visited;
    if (node->value >= lo && node->value <= hi) s.sum += node->value;
    full_scan(node->left.get(), lo, hi, s);
    full_scan(node->right.get(), lo, hi, s);
}

The Stats struct holds two numbers, the running sum and the visit count. The function passes the same Stats object down the recursion, so every call adds to one total.

Now build the tree and run the scan. The values are inserted in the order 8, 3, 10, 1, 6, 14, 4, 7, 13, which gives the tree drawn above.

int main() {
    std::unique_ptr<Node> root;
    for (int v : {8, 3, 10, 1, 6, 14, 4, 7, 13}) root = insert(std::move(root), v);
 
    Stats slow;
    full_scan(root.get(), 5, 13, slow);
    std::cout << "full scan: sum=" << slow.sum << " visited=" << slow.visited << "\n";
}

Output:

full scan: sum=44 visited=9

The answer is right, but the scan visited all nine nodes. It did not use the ordering at all. For a tree of one million values, it would visit one million nodes for every query, even a query for a range that contains only three values.

The idea: a subtree can be skipped

Look at one node, with value v, and the range lo to hi. There are three cases.

• If v is less than lo, then v is too small. Every value in the left subtree is smaller than v, so every value there is also too small. Skip the left subtree. Only the right subtree can hold values in the range.
• If v is greater than hi, then v is too large. Every value in the right subtree is larger than v, so every value there is too large. Skip the right subtree. Only the left subtree can hold values in the range.
• If v is between lo and hi, the node is in the range. Add v to the sum. Both subtrees might hold more values in the range, so visit both.

This is called pruning. Pruning means cutting off a branch of the search because it cannot give an answer. The name comes from cutting branches off a real tree.

Here is the same query, traced one node at a time, for the range 5 to 13.

1. Visit 8. It is between 5 and 13. Add 8. Visit both sides.
2. Go left to 3. Three is less than 5, so skip 3's left subtree. That subtree holds only the node 1, which is never visited. Go right to 6.
3. Visit 6. It is in the range. Add 6. Visit both sides.
4. Go left from 6 to 4. Visit 4. It is less than 5, so go right only. Node 4 has no children, so this branch ends.
5. Go right from 6 to 7. It is in the range. Add 7. Both children are missing, so this branch ends.
6. Back at 8, go right to 10. It is in the range. Add 10. Visit both sides.
7. Go left from 10. There is no left child, so nothing happens. Go right to 14.
8. Visit 14. It is greater than 13, so skip 14's right subtree. Go left to 13.
9. Visit 13. It is in the range. Add 13. Both children are missing, so the query is done.

The visited nodes were 8, 3, 6, 4, 7, 10, 14 and 13. That is eight nodes. The only node not visited was 1, which was skipped with 3's left subtree. The added values are 8, 6, 7, 10 and 13, and their sum is 44. Node 4 was visited but not added, because it is outside the range.

Code for the pruned search

The pruned version follows the three cases above exactly. It adds a value only when the value is in the range, and it recurses into only the side that can hold more matches.

void range_sum_into(const Node* node, int lo, int hi, Stats& s) {
    if (node == nullptr) return;
    ++s.visited;
    if (node->value < lo) {
        range_sum_into(node->right.get(), lo, hi, s);
        return;
    }
    if (node->value > hi) {
        range_sum_into(node->left.get(), lo, hi, s);
        return;
    }
    s.sum += node->value;
    range_sum_into(node->left.get(), lo, hi, s);
    range_sum_into(node->right.get(), lo, hi, s);
}

The first two if blocks are the pruning. Each one returns after recursing into a single child. The last part handles the in-range case, where both children are visited.

Add this call to main after the full scan:

    Stats fast;
    range_sum_into(root.get(), 5, 13, fast);
    std::cout << "pruned:    sum=" << fast.sum << " visited=" << fast.visited << "\n";

Output:

full scan: sum=44 visited=9
pruned:    sum=44 visited=8

The sums match. The pruned search visited one node fewer, because it skipped node 1. On a tiny tree that is a small saving. The saving grows with the size of the tree, as the next examples show.

Second example: a narrow range

Now use a range that contains a single value, 7 to 7. The answer is 7, so the query needs to find that one node.

Trace the search from the root.

• At 8, the value is greater than 7. Skip the right subtree, which holds 10, 13 and 14. Those three nodes are never visited.
• Go left to 3. The value is less than 7. Skip the left subtree, which holds 1. Go right to 6.
• At 6, the value is less than 7. Skip the left subtree, which holds 4. Go right to 7.
• At 7, the value is in the range. Add 7. Both children are missing.

The visited nodes are 8, 3, 6 and 7. The skipped nodes are 10, 14, 13, 1 and 4. Five nodes were skipped and four were visited. A full scan would have visited all nine.

    Stats one;
    range_sum_into(root.get(), 7, 7, one);
    std::cout << "range [7, 7]: sum=" << one.sum << " visited=" << one.visited << "\n";

Output:

range [7, 7]: sum=7 visited=4

Look at the path. The search went from the root toward 7 along one line of nodes, and it looked at a few side nodes on the way. That is the general pattern for a narrow range in a balanced tree. The work follows the two search paths, one toward lo and one toward hi, and the nodes inside the range. A narrow range has two close search paths and few nodes inside it, so the query is short.

Third example: a range that finds nothing

Use the range 20 to 30. No value in the tree is in that range. The answer is 0.

At the root, 8 is less than 20, so skip the left subtree. Go right to 10. Ten is less than 20, so skip its left subtree, which is empty. Go right to 14. Fourteen is less than 20, so skip its left subtree and go right. The right child is missing, so the search ends.

The search visited three nodes. It never looked at the left half of the tree. Nothing was added.

    Stats none;
    range_sum_into(root.get(), 20, 30, none);
    std::cout << "range [20, 30]: sum=" << none.sum << " visited=" << none.visited << "\n";

Output:

range [20, 30]: sum=0 visited=3

A query that finds nothing still needs a path from the root to the place where the answer would be. Here the path is 8, 10, 14. This is why the visit count is a better measure than the sum. The sum is 0 in both a fast query and a slow one.

Fourth example: sorted input gives a chain

The pruning works only when the tree is balanced. Insert the values 1 to 10 in order and the tree becomes a chain. Each node has no left child and one right child. The root is 1, its right child is 2, and so on down to 10.

1
 \
  2
   \
    3
     \
      ...

A search in this tree walks down one node at a time. Every value below lo lies on the path, and the search must step past each one, because the path is the only way to reach the range. Pruning can skip a left subtree, but in a chain the left subtrees are empty, so there is nothing to skip.

Run the range 4 to 7 on this tree.

void chain_example() {
    std::unique_ptr<Node> root;
    for (int v = 1; v <= 10; ++v) root = insert(std::move(root), v);
    Stats s;
    range_sum_into(root.get(), 4, 7, s);
    std::cout << "sorted input 1..10, range [4, 7]: sum=" << s.sum << " visited=" << s.visited << "\n";
}

Output:

sorted input 1..10, range [4, 7]: sum=22 visited=8

The sum is 4 + 5 + 6 + 7, which is 22. The query visited eight nodes, which is more than the four matches and far more than the ideal. It had to walk through 1, 2 and 3 to reach the range, and it visited 8 as the first node past the range. In a chain of one million values, a query for values near the top would walk past almost a million nodes. The lesson on why sorted input makes a BST a chain explains where this comes from and how to avoid it.

How much work a query does

Count the visited nodes for the three kinds of range you have seen.

The table shows a pattern, but it is only nine nodes. The real lesson is what happens as the tree grows. A query visits:

• the nodes on the path toward lo,
• the nodes on the path toward hi, and
• the nodes inside the range.

Two paths in a balanced tree are short. If the tree has about 20 levels, each path has about 20 nodes. So a narrow range in a balanced tree costs about 40 visits plus the number of matches. This is far less than a million for a tree with a million nodes.

A wide range is different. If the range covers almost every value, almost every node is inside it, and pruning skips very little. Then the visit count is close to the size of the tree, just as with the full scan. Pruning helps most with narrow and medium ranges.

Checking the code with random trees

A single example can hide a bug. The check below builds 300 random trees, runs 50 random queries on each, and compares the pruned answer with the full scan. Random values range from -50 to 50, so duplicates happen often, and the duplicates are ignored by the insert code.

#include <algorithm>
#include <random>
#include <vector>
 
int random_check() {
    std::mt19937 rng(12345);
    std::uniform_int_distribution<int> value_dist(-50, 50);
    int checks = 0;
    int failures = 0;
    for (int round = 0; round < 300; ++round) {
        std::unique_ptr<Node> tree;
        int n = std::uniform_int_distribution<int>(1, 60)(rng);
        for (int i = 0; i < n; ++i) tree = insert(std::move(tree), value_dist(rng));
        for (int q = 0; q < 50; ++q) {
            int a = value_dist(rng), b = value_dist(rng);
            int lo = std::min(a, b), hi = std::max(a, b);
            Stats expected;
            full_scan(tree.get(), lo, hi, expected);
            Stats got;
            range_sum_into(tree.get(), lo, hi, got);
            if (got.sum != expected.sum) ++failures;
            ++checks;
        }
    }
    std::cout << "random checks: " << checks << ", failures: " << failures << "\n";
    return failures;
}

Output:

random checks: 15000, failures: 0

The pruned version returned the same sum as the full scan on all 15,000 queries. A test like this is cheap to write, and it catches the mistakes described in the next section.

Common mistakes

Pruning on the wrong side

The most common mistake is swapping the two directions. When the value is too small, the search must go right, because the right side holds the larger values. A version that goes left in that case visits the wrong nodes and misses the answer.

Here is a version with the directions swapped. It is wrong on purpose, so you can see the output.

void wrong_directions(const Node* node, int lo, int hi, Stats& s) {
    if (node == nullptr) return;
    ++s.visited;
    if (node->value < lo) {
        wrong_directions(node->left.get(), lo, hi, s);
        return;
    }
    if (node->value > hi) {
        wrong_directions(node->right.get(), lo, hi, s);
        return;
    }
    s.sum += node->value;
    wrong_directions(node->left.get(), lo, hi, s);
    wrong_directions(node->right.get(), lo, hi, s);
}

Run it on the range 5 to 13:

wrong directions, range [5, 13]: sum=18 visited=5

The correct sum is 44. The wrong version returned 18, which is 8 plus 10. It missed 6, 7 and 13. In the random check, the wrong version disagreed with the full scan on 12,449 of the 15,000 queries. A bug like this often gives a plausible-looking number, so compare with a full scan on small trees before you trust a pruned search.

Using the wrong comparison at the edges

The range includes both ends. A value equal to lo must be added. If you write the first test as node->value <= lo, a node whose value equals lo is treated as too small. The search then skips its left side and also misses the node itself, so its value is lost. Use < for the first test and > for the second, as in the code above.

Adding before checking the range

Some people write s.sum += node->value; before the if tests. The value is then added even when it is outside the range. The fix is to put the addition after the two pruning checks, as in the code above.

Forgetting that the root can be missing

If the tree is empty, the root is nullptr. The first line of the function handles that case. Remove that line and the code dereferences a null pointer when it reads node->value. On most systems that crashes the program.

A compile error when inserting

The insert function must pass its child pointer with std::move. A std::unique_ptr cannot be copied, so the compiler rejects a copy. This version forgets the move:

std::unique_ptr<Node> insert(std::unique_ptr<Node> root, int value) {
    if (!root) return std::make_unique<Node>(value);
    if (value < root->value) root->left = insert(root->left, value);
    return root;
}

Compiling it with g++ -std=c++20 -Wall gives this error. The file and line numbers come from the test file used to check it.

mistake_copy.cpp:12:49: 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>]'

The message says that the copy constructor is deleted. In plain words, the compiler will not make a second owner for the same node. The fix is insert(std::move(root->left), value).

Practice

Exercise 1

Use the example tree from this lesson. Predict the sum and the number of visited nodes for the range 4 to 10. Then check your answer with the pruned function.

Show the answer

The values in the range are 4, 6, 7, 8 and 10. The sum is 35. The visited nodes are 8, 3, 6, 4, 7, 10, 14 and 13, which is 8 nodes. The node 1 is skipped under 3. The output is sum=35 visited=8.

Exercise 2

Use the tree of values 1 to 10 inserted in order. Predict the sum and the visited count for the range 2 to 4. Explain why the query visits more nodes than it adds.

Show the answer

The values in the range are 2, 3 and 4, so the sum is 9. The visited nodes are 1, 2, 3, 4 and 5. Node 1 is less than 2, so the search goes right past it. Node 5 is greater than 4, so the search goes left from it and finds nothing. The output is sum=9 visited=5. The query visits more nodes than it adds because the path from the root must pass through the values below the range.

Exercise 3

Predict the visited count for a range that covers every value in the example tree, such as 0 to 100. Explain your answer in terms of pruning.

Show the answer

The visited count is 9, which is every node. Every node is in the range, so no subtree is pruned. Both children are visited each time, and the search visits the whole tree. This is the worst case for pruning.

Exercise 4

Change the function so it counts the values in the range instead of summing them. Keep the same pruning rules. Give the new function and show the output for the range 5 to 13 on the example tree.

Show the answer

Add a long long count field to Stats and increment it instead of adding to the sum. The function body becomes:

void range_count_into(const Node* node, int lo, int hi, Stats& s) {
    if (node == nullptr) return;
    ++s.visited;
    if (node->value < lo) {
        range_count_into(node->right.get(), lo, hi, s);
        return;
    }
    if (node->value > hi) {
        range_count_into(node->left.get(), lo, hi, s);
        return;
    }
    ++s.count;
    range_count_into(node->left.get(), lo, hi, s);
    range_count_into(node->right.get(), lo, hi, s);
}

The values in the range are 6, 7, 8, 10 and 13, so the count is 5. The visited count is still 8, because the pruning rules did not change.

Summary

• A range sum adds every value between lo and hi, with both ends included.
• A full scan visits every node. Pruning skips a subtree when its root is too small or too large.
• The pruned search visits the nodes on the path toward lo, the path toward hi, and the nodes inside the range.
• Count visited nodes to see the saving. Narrow ranges save the most in a balanced tree, and a tree built from sorted input gives little saving.
• Test a pruned search against a full scan on random trees, because a swapped direction gives a wrong answer that looks plausible.