Trim a BST to a range

Why this matters

Suppose a shop keeps the prices of its products in a binary search tree, and a report needs only the products priced between 5 and 13 pounds. The program could search for each price and build a new tree, or it could cut away the parts of the existing tree that are outside the range. Cutting is often faster and uses less code, because most of the tree that survives is already in the right shape.

This operation is called trimming. It keeps every node whose value is inside a range [low, high], which includes the two end values, and it removes every other node. The result must still be a valid binary search tree, which means every node is larger than everything in its left subtree and smaller than everything in its right subtree.

The lesson uses the rule from the earlier lessons on binary search trees. It does not repeat how to insert or delete a single node. It also does not rely on the trees being balanced. The method works on any valid BST.

The idea: throw away whole subtrees

A node tells you a lot about the nodes below it. Take a node with value 3 in a tree where the range is 5 to 13. The value 3 is too small. In a valid BST, everything in its left subtree is smaller than 3, so everything there is also too small. Only the right subtree can still hold values in range. So the program can drop the node and its entire left subtree at once, and continue with the right subtree.

The same thinking works in the other direction. A node with value 20 is too large. Everything in its right subtree is larger than 20, so the right subtree can go. Only the left subtree can still hold values in range.

A node whose value is inside the range stays. Its left and right subtrees may both contain values outside the range, so the program trims each of them the same way.

Here is the rule in three lines:

• If the node is too small, keep only the result of trimming its right side.
• If the node is too large, keep only the result of trimming its left side.
• If the node is in range, trim both sides and keep the node.

Example 1: a tree with a simple range

Insert the values 8, 3, 10, 1, 6, 14, 4, 7 and 13 into an empty tree, in that order. The root is 8. Its left subtree holds 3, 1, 6, 4 and 7. Its right subtree holds 10, 14 and 13. The inorder walk prints the values in sorted order: 1 3 4 6 7 8 10 13 14.

Trim the tree to the range 5 to 13. Work through the nodes from the root:

• Node 8 is in range, so it stays. Trim both sides.
• Node 3 is too small. Drop it and its left subtree, which holds 1. Keep the result of trimming its right child, which is 6.
• Node 6 is in range, so it stays. Its left child 4 is too small, so 4 is dropped and nothing is left on that side. Its right child 7 is in range, so it stays.
• Node 10 is in range, so it stays. Its left side is empty. Its right child 14 is too large, so 14 is dropped and its left child 13 is kept, because 13 is in range.

The surviving values are 6, 7, 8, 10 and 13. Their inorder walk is 6 7 8 10 13. The tree still obeys the BST rule, because nothing was moved. Only whole pieces were cut off.

A recursive trim

The recursive version follows the three rules directly. A function called trim takes a node and the range, and returns the root of the trimmed subtree. The caller then uses that returned value to fix its own child pointer.

The program needs one more helper. When the function drops a subtree, it must free the memory that subtree uses. In C++, memory created with new stays in use until your code calls delete on it. If nothing deletes it, the memory is leaked. The helper destroy walks a subtree and deletes every node in it.

The program builds each tree fresh, trims it, prints the result and frees it. Compile it with the sanitizer flags shown in the Practice section, or with plain g++ -std=c++20 -Wall. The output is:

Example 1: keep 5 to 13
recursive:  6 7 8 10 13
iterative:  6 7 8 10 13
empty range: 
Example 2: the root is out of range
iterative:  6
recursive:  6
Example 3: a chain of small values under the root
before:     2 4 6 10 12 14
iterative:  6 10 12
recursive:  6 10 12

The empty range line is blank because a range of 20 to 30 keeps nothing. The function returns nullptr, which means no tree is left, and the walk prints no values.

Reading the recursive code

The first check is the empty tree. If the node is nullptr, there is nothing to trim, so the function returns nullptr.

The next two branches handle the removed nodes. In the node->val < low branch, the program first trims the right side and stores the result in keep. Then it destroys the left subtree, which is entirely too small, and deletes the node itself. It returns keep, which becomes the new subtree root in the caller. The order matters. The right side is read before the node is deleted, so the program never reads freed memory.

The last part handles the node in range. Both children are replaced by the results of trimming them. The caller stores the returned pointer in node->left or node->right, which is why the assignment is needed. Without it, the parent would keep pointing at a node that was already deleted.

Example 2: when the root itself is out of range

Example 1 never removes the root. Example 2 does. The tree is built from 3, 1, 4 and 6. Its root is 3, with 1 on the left and 4 on the right, and 6 on the right of 4. The range is 5 to 9, so the root 3 must go.

The root is out of range, so the new root must come from one of its subtrees. Since 3 is too small, everything on its left is also too small, so the program drops 3 and 1 and looks at the right side. The right child is 4, which is still too small. So 4 is dropped too, and the program looks at 6, which is in range. Node 6 becomes the new root, and its tree has no other nodes. The output is 6.

This is why the iterative version has a loop at the very start. It moves the root down until it finds a node inside the range. Each step drops the current root and its side that is out of range. The recursive version handles the same case through its first two branches, so it also prints 6.

Example 3: a chain that needs a loop

Example 3 shows why the iterative version has a second loop. The tree is built from 10, 2, 4, 6, 12 and 14. The root is 10, and its left child is 2. Node 2 has a right child, 4, which has a right child, 6. The left side of the root is a chain of three values, 2, 4 and 6, and only 6 is in range for a range of 5 to 12.

The root 10 is in range, so the program keeps it and works on its children. The left child 2 is too small. The program must not stop after removing 2, because the new left child, 4, is also too small. The loop while (n->left && n->left->val < low) keeps replacing the left child with its own right child until the left child is in range or missing. That loop replaces 2 with 4 and then 4 with 6, and it stops at 6.

The recursive version reaches the same answer in a different way. The call trim(node->right, low, high) in the too-small branch keeps working down the chain, so it also drops 2 and 4 without a loop. The output for both is 6 10 12.

The iterative version

The recursive version uses the call stack, the memory the computer uses to remember which call is waiting for which. A very tall tree could make the recursion too deep. The iterative version avoids this by keeping its own list of nodes still to check, which is the vector named stack.

The steps are:

1. Move the root down while it is out of range. Free each node that is skipped, together with the side that is also out of range.
2. Put the root on the list.
3. Take a node off the list. Remove any left child that is too small by replacing it with its right child, and free the removed node and its left side. Do the same for any right child that is too large.
4. Put the remaining children on the list, so they are checked later.
5. Stop when the list is empty and return the root.

Step 3 needs care. After the two loops, every child that is still attached is in range. The left child is at least low, and it is smaller than its parent, which is at most high, so it cannot be too large. The right child is at most high, and it is larger than its parent, which is at least low, so it cannot be too small. That is why the left side only checks low, and the right side only checks high.

Common mistakes

Mistake 1: not using the returned pointer

The recursive trim returns a new root. If the caller ignores it, the parent still points at the old node. The next function does this on purpose. The test program builds a root 3 with left child 1 and right child 6, then trims with a range that starts at 5:

Node* trimBad(Node* node, int low) {
    if (!node) return nullptr;
    if (node->val < low) {
        Node* keep = trimBad(node->right, low);
        delete node;
        destroy(node->left);
        return keep;
    }
    return node;
}

The root 3 is too small, so the program deletes it. The function then reads node->left after delete node, which is a read of freed memory. Here is the real report from AddressSanitizer, a tool that checks memory use while the program runs. It was built with -fsanitize=address and run on this code:

==600437==ERROR: AddressSanitizer: heap-use-after-free on address 0x783829fe0048 at pc 0x62d297c4c943 bp 0x7ffd164d2930 sp 0x7ffd164d2920
READ of size 8 at 0x783829fe0048 thread T0
    #0 0x62d297c4c942 in trimBad(Node*, int) bug.cpp:109

The addresses differ on each run, and the directory part of the file path is left out here. The line that matters is the first #0 line, which names the function and the line in the source file where the freed memory was read.

Mistake 2: forgetting to store the returned value

The second mistake is a missing assignment. The next function calls trim on the left child but does not store the result:

trim(node->left, low, high);
node->right = trim(node->right, low, high);

If the left child is removed, node->left still holds the old address, which now points at freed memory. The fix is to write node->left = trim(node->left, low, high);. The bug is easy to miss because the code compiles and often runs, and the bad read may give the right answer by luck. A sanitizer checks every read, so running with -fsanitize=address reports it. Here is the real report for a tree with root 8, left child 3 (which has right child 6) and right child 10, trimmed to the range 5 to 13. The addresses and line numbers differ on each run and in your file, and the directory part of the path is left out:

==600043==ERROR: AddressSanitizer: heap-use-after-free on address 0x79a0a1be0078 at pc 0x5fdab09dc618 bp 0x7ffd1b81c630 sp 0x7ffd1b81c620
READ of size 8 at 0x79a0a1be0078 thread T0
    #0 0x5fdab09dc617 in inorder(Node const*, std::vector<int, std::allocator<int> >&) bug2.cpp:21
    #1 0x5fdab09dc62e in inorder(Node const*, std::vector<int, std::allocator<int> >&) bug2.cpp:21
    #2 0x5fdab09ddd45 in main bug2.cpp:130

Mistake 3: deleting a node before reading its children

In each removal branch of the recursive version, the code first reads the child it keeps and destroys the other child, and only then calls delete on the node. If the order is changed so that delete node; comes first, the next read of node->left or node->right reads freed memory, just as in mistake 1. Read everything you need from a node, then delete it.

Mistake 4: a range that is not inclusive

The range [low, high] includes both ends. A node with value 5 is kept when the range is 5 to 13. Keep the comparisons strict: remove a node only when its value is < low or > high. Writing <= low would remove a node that sits exactly on the boundary.

Mistake 5: checking only one side of the range

A common error is to write only the check for the lower bound, low, and forget the upper bound, high. Then the tree keeps values that are too large. The two branches of the recursive version look alike, but each one handles a different bound, so they are easy to mix up when copying code.

Practice

Use the sanitizer flags -fsanitize=address,undefined -g when you run the exercises. The tool reports any freed memory that is read again, and any memory that is never freed.

Exercise 1

Build a tree by inserting 5, 3, 8, 1, 4, 9 and 2 in that order. Trim it to the range 4 to 8. Write the inorder walk of the result.

Show the answer

The tree has root 5, with left child 3 and right child 8. Node 3 has left child 1 and right child 4, and node 1 has right child 2. Node 8 has right child 9.

The root 5 is in range and stays. Its left child 3 is too small, so 3 is dropped with its whole left subtree, which holds 1 and 2. The program keeps the result of trimming 3's right child, which is 4, and 4 is in range. The root's right child 8 is in range and stays. Its right child 9 is too large, so 9 is dropped. The result is 5 with children 4 and 8. The inorder walk is 4 5 8.

Exercise 2

For the same tree as exercise 1, what changes if the range is 6 to 8? Give the inorder walk.

Show the answer

The root 5 is too small. The program drops 5 and its left side, which holds 3, 1, 4 and 2. It then looks at the right child 8, which is in range, so 8 becomes the root. Node 8's right child 9 is too large and is dropped. The result is a single node, 8, and the walk is 8.

Exercise 3

Write the function int countRemoved(const Node* root, int low, int high) that returns the number of nodes a trim would remove, without changing the tree.

Show the answer

A trim removes exactly the nodes whose values are outside the range, and keeps every node inside it. So the function only needs to count the nodes outside the range:

int countRemoved(const Node* n, int low, int high) {
    if (!n) return 0;
    int here = (n->val < low || n->val > high) ? 1 : 0;
    return here + countRemoved(n->left, low, high) + countRemoved(n->right, low, high);
}

For the tree from Example 1, with values 8, 3, 10, 1, 6, 14, 4, 7 and 13 and the range 5 to 13, the answer is 4. The removed values are 3, 1, 4 and 14, and the function counts exactly those. This version never changes the tree, so it can be called before a trim.

Exercise 4

Find the bug in this function, which tries to trim a tree but leaves a node that is too small:

Node* trimLow(Node* node, int low) {
    if (!node) return nullptr;
    if (node->val < low) return node->right;
    node->left = trimLow(node->left, low);
    return node;
}

Show the answer

There is one bug and one leak. When the node is too small, the function returns node->right without trimming it, so a too-small value in that right subtree stays in the tree. For example, with root 3, right child 4 and low set to 5, the 4 stays. The removed node and its left subtree are also never freed, which leaks memory. The fix keeps the trimmed right side, frees the node, and returns the kept side:

Node* keep = trimLow(node->right, low);
destroy(node->left);
delete node;
return keep;

The in-range branch is correct. Every value in the right subtree is larger than the node, so it is already at least low.

Exercise 5

Predict the output for the tree built from 15, 5, 12, 30 in that order, trimmed to the range 10 to 20. Then say which nodes are freed.

Show the answer

The root 15 is in range. Its left child 5 is too small, so 5 is freed and the program keeps the result of trimming its right child 12, which is in range and stays. The right child 30 is too large, so 30 is freed and the program keeps the result of trimming its left child, which is nothing. The result is 15 with left child 12, and the inorder walk is 12 15. The freed nodes are 5 and 30.

Summary

• Trimming removes whole subtrees: a node that is too small takes its left side with it, and a node that is too large takes its right side with it.
• The recursive trim returns the new root of each subtree, and the caller must store that value in its child pointer.
• The iterative version first moves the root into range, then checks each node's children on a stack.
• Free every removed node with delete, after reading the children you still need.
• Run the code with -fsanitize=address to catch reads of freed memory that a normal run may not show.