Why this matters
Most binary search tree bugs do not crash the program. The program runs, prints numbers, and gives wrong answers. A search returns "not found" for a value that is in the tree. A count is one too high. A delete removes one value and also quietly removes others. Nothing in the output looks like an error unless you already know the right answer.
This lab gives you a binary search tree with three bugs. You will run it, read the output against the expected values, find each bug from its symptom, and fix it. The bugs are typical for hand-written trees, and they are the kind that show up in code review or when an interviewer asks you to trace a small example by hand.
You need the basic insert, search and delete operations from the earlier lessons in this module. This lab does not explain them again. It is about finding out what is wrong when the code does not do what you expect.
A method for finding bugs
Before you read the code, set up the checks. A check is a small piece of code that compares what the program does with what it should do. The checks in this lab use these steps:
- Write the expected value next to each line of output. The program prints
(expected true)for that reason. - Print the state, not only the answer. The lab prints the keys in sorted order, so you can see what the tree holds. A search that returns the wrong answer is easier to explain when you can see the stored values.
- Check the rule the tree must always follow. For a binary search tree, every key in a left subtree is smaller than its node, and every key in a right subtree is larger. The lab's
is_validfunction checks this rule for the whole tree. - Find the one branch of code that handles the failing case. Trace one small example through that branch by hand, step by step.
- Change one thing, then run the checks again. If you change several things at once, you cannot tell which change fixed the problem.
The buggy program
The program below defines Bst, a class that stores integer keys. Each tree node owns its children through std::unique_ptr, a C++ smart pointer. A std::unique_ptr deletes the node it owns when it goes out of scope, so there are no delete calls to forget.
The program contains three bugs. Try to find them before you read the explanations below.
#include <iostream>
#include <memory>
#include <optional>
#include <vector>
struct Node {
int key;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
explicit Node(int k) : key(k) {}
};
class Bst {
public:
void insert(int key) {
root_ = insert_into(std::move(root_), key);
++size_;
}
bool contains(int key) const {
const Node* cur = root_.get();
while (cur != nullptr) {
if (key > cur->key) {
cur = cur->left.get();
} else if (key < cur->key) {
cur = cur->right.get();
} else {
return true;
}
}
return false;
}
void erase(int key) {
root_ = erase_from(std::move(root_), key);
}
std::size_t size() const {
return size_;
}
std::vector<int> keys() const {
std::vector<int> out;
collect(root_.get(), out);
return out;
}
bool is_valid() const {
return valid_range(root_.get(), kLow, kHigh);
}
private:
static constexpr long long kLow = -4000000000LL;
static constexpr long long kHigh = 4000000000LL;
std::unique_ptr<Node> root_;
std::size_t size_ = 0;
static std::unique_ptr<Node> insert_into(std::unique_ptr<Node> node, int key) {
if (!node) {
return std::make_unique<Node>(key);
}
if (key < node->key) {
node->left = insert_into(std::move(node->left), key);
} else {
node->right = insert_into(std::move(node->right), key);
}
return node;
}
static std::unique_ptr<Node> erase_from(std::unique_ptr<Node> node, int key) {
if (!node) {
return nullptr;
}
if (key < node->key) {
node->left = erase_from(std::move(node->left), key);
return node;
}
if (key > node->key) {
node->right = erase_from(std::move(node->right), key);
return node;
}
if (!node->left) {
return nullptr;
}
if (!node->right) {
return std::move(node->left);
}
const Node* succ = node->right.get();
while (succ->left) {
succ = succ->left.get();
}
node->key = succ->key;
node->right = erase_from(std::move(node->right), succ->key);
return node;
}
static void collect(const Node* node, std::vector<int>& out) {
if (!node) {
return;
}
collect(node->left.get(), out);
out.push_back(node->key);
collect(node->right.get(), out);
}
static bool valid_range(const Node* node, long long low, long long high) {
if (!node) {
return true;
}
if (node->key <= low || node->key >= high) {
return false;
}
return valid_range(node->left.get(), low, node->key) && valid_range(node->right.get(), node->key, high);
}
};
void print_keys(const Bst& t) {
std::cout << "keys:";
for (int k : t.keys()) {
std::cout << ' ' << k;
}
std::cout << '\n';
}
int main() {
Bst t;
for (int k : {5, 3, 8, 3, 9, 1}) {
t.insert(k);
}
std::cout << "size after inserting 5 3 8 3 9 1: " << t.size() << " (expected 5)\n";
print_keys(t);
std::cout << "valid: " << std::boolalpha << t.is_valid() << "\n";
std::cout << "contains 3: " << t.contains(3) << " (expected true)\n";
std::cout << "contains 8: " << t.contains(8) << " (expected true)\n\n";
Bst u;
for (int k : {5, 3, 8, 9}) {
u.insert(k);
}
u.erase(8);
std::cout << "after erasing 8 from 5 3 8 9:\n";
print_keys(u);
std::cout << "valid: " << u.is_valid() << " (expected true)\n";
return 0;
}Save the program as bst_buggy.cpp. Compile it with warnings on and run it:
g++ -std=c++20 -Wall -Wextra -o bst_buggy bst_buggy.cpp && ./bst_buggyCompilation prints no warnings. The output is:
size after inserting 5 3 8 3 9 1: 6 (expected 5)
keys: 1 3 3 5 8 9
valid: false
contains 3: false (expected true)
contains 8: false (expected true)
after erasing 8 from 5 3 8 9:
keys: 3 5
valid: true (expected true)The compiler is silent because the code is valid C++. Warnings catch mistakes in the language, such as an unused variable or a wrong type. They cannot know what the tree is supposed to do. The bugs below are logic bugs, so the checks are what find them.
Bug 1: a duplicate is stored and counted
The first output line says the size is 6, but the program inserted six values, and one of them, 3, was already in the tree. The keys line shows 3 twice. The tree stores the duplicate as a second node.
Look at insert. It adds one to size_ every time, even when the key is already present. Look at insert_into too. When the key equals the node's key, the else branch runs, and the key is added on the right. So the duplicate becomes a real second node.
Trace the six inserts by hand to see exactly where the duplicate goes. After inserting 5, the tree is just 5. Then:
- Insert 3. Since 3 is less than 5, it becomes the left child of 5.
- Insert 8. Since 8 is greater than 5, it becomes the right child of 5.
- Insert 3 again. At 5, the code goes left to the first 3. At that node the new key is not less than 3, so the
elsebranch runs, and the new 3 becomes the right child of the first 3. - Insert 9. It goes right at 5, then right at 8.
- Insert 1. It goes left at 5, then left at the first 3.
The keys in order are 1, 3, 3, 5, 8, 9, which is the keys line in the output. The tree stores six nodes, and the size counter also says six.
The program was meant to store a set of keys, where each key appears once. Two changes are needed. The insert must not add a node when the key is already present, and the size must go up only when a node is made. The fixed version passes a flag down the recursion, and the flag is set only when a new node is created:
static std::unique_ptr<Node> insert_into(std::unique_ptr<Node> node, int key, bool& added) {
if (!node) {
added = true;
return std::make_unique<Node>(key);
}
if (key < node->key) {
node->left = insert_into(std::move(node->left), key, added);
} else if (key > node->key) {
node->right = insert_into(std::move(node->right), key, added);
}
return node;
}When the key equals the node's key, neither branch runs, and the function returns the node unchanged. The public insert then increments size_ only when the flag is set:
void insert(int key) {
bool added = false;
root_ = insert_into(std::move(root_), key, added);
if (added) {
++size_;
}
}The is_valid check also reports this bug. The second 3 sits in the right subtree of the first 3, and the rule says a key in a right subtree must be larger than its parent. The check uses strict bounds, so an equal key fails. That is why the first line of the output says valid: false.
Bug 2: search goes the wrong way
The output says contains 3 and contains 8 are both false, but both values were inserted. Look at the loop in contains:
if (key > cur->key) {
cur = cur->left.get();
} else if (key < cur->key) {
cur = cur->right.get();
}Trace contains(8) on a tree with root 5, a left child 3 and a right child 8. The root is 5. Since 8 is greater than 5, the first test is true, so the code moves to the left child, which is 3. Since 8 is greater than 3, the code again moves to the left child of 3, which is empty. The loop stops and returns false.
The comparisons are reversed. Larger keys belong on the right, and smaller keys on the left. The fixed loop tests the smaller case first:
if (key < cur->key) {
cur = cur->left.get();
} else if (key > cur->key) {
cur = cur->right.get();
} else {
return true;
}After this change, contains(8) goes right from 5 and finds 8.
A search that returns false for a key that was inserted is usually a flipped comparison or a wrong branch. Trace one small example by hand before you change anything.
Bug 3: a delete drops a whole subtree
The second test erases 8 from the tree 5, 3, 8, 9. Node 8 has no left child and has a right child, 9. The expected keys after the delete are 3, 5 and 9. The output shows only 3 and 5, so 9 was lost.
The cause is this code inside erase_from, which runs once the node to delete has been found:
if (!node->left) {
return nullptr;
}When the node has no left child, the code returns nullptr, which means the function returns no subtree at all. If the node had a right child, that right child is dropped with the node. The right child of 8 is 9, so 9 disappears from the tree.
The fix is to return the right child in this case, because it is the only child the node has:
if (!node->left) {
return std::move(node->right);
}The check after it handles a missing right child: the left child takes the node's place. If both children are missing, the first check returns std::move of the empty right pointer, which is nullptr. That is correct for a leaf.
Look at the output again. After the bug, valid still says true. The tree is still a correct binary search tree. It has fewer keys than it should. The order rule cannot detect a missing key, so is_valid cannot catch this kind of bug. The check that catches it is the comparison of keys() with the list you expect.
Bug 3 again: a delete with two children
Bug 3 also appears in a delete with two children, which is the harder case in the code. Build a tree by inserting 5, 3, 8, 2, 4 and 9 in that order. The root is 5, its left child is 3 with children 2 and 4, and its right child is 8 with 9 on its right. Erasing 5 means the node has two children.
The delete code handles two children by finding the smallest key in the right subtree, which is 8 here. It copies 8 into the root, and then deletes the old node with key 8 from the right subtree. That second delete is where the bug shows. The old node 8 has no left child and has 9 on its right, so the buggy line returns nullptr and 9 is dropped.
Running the buggy version with this input prints:
keys: 2 3 4 8
valid: true
contains 4: false contains 9: falseThe keys line shows that 9 is lost. The two contains answers are false too, but they come from bug 2 as well, so this output mixes two bugs. The same fix from bug 3 handles this case, because the old node 8 has only a right child, and that child takes its place. The fixed version prints:
keys: 2 3 4 8 9
valid: true
contains 4: true contains 9: trueThe lesson for debugging is that one bug can show up in several places. Check every path that calls the buggy line, not only the first one you tried.
Checking the fixed program
After the three changes, the program prints this output:
size after inserting 5 3 8 3 9 1: 5 (expected 5)
keys: 1 3 5 8 9
valid: true
contains 3: true (expected true)
contains 8: true (expected true)
after erasing 8 from 5 3 8 9:
keys: 3 5 9
valid: true (expected true)Every line now matches the expected value. Both keys lines changed: the first lost the duplicate 3, and the second kept 9. The valid line in the first test changed because the duplicate is gone, and the contains lines changed because the search now goes the right way.
Common mistakes when debugging a tree
Changing the expected value to match the output. If the output says size 6 and you expected 5, the code is wrong unless you have a reason to think the expectation is wrong. Write the expected value from the problem statement, not from the output.
Assuming the bug is where the symptom shows. A wrong answer from contains can also come from a bad insert. If insert puts a key in the wrong subtree, a correct search still cannot find it. Trace a small example through both functions before you decide which one is wrong.
Testing with one input. A test that inserts only 5 and then checks contains(5) passes on the buggy program. So do the size and the keys for that input. None of the three bugs shows up with a single value, because each bug needs a second key: a duplicate, a left or right move from a node that is not the root, or a node with a right child to lose. Choose inputs that make each branch run at least once.
Stopping after the first fix. After you fix bug 1, the first line of output changes, but the contains lines still fail. Run the whole program again after every change, because a fix in one place can leave a failure elsewhere.
Expecting the compiler to find logic errors. The buggy program compiles with no warnings under -Wall -Wextra. A compiler warning helps with typos, unused variables and some type errors. It cannot tell you that a comparison points the wrong way.
Trusting is_valid for every delete bug. The order rule still holds when a key is lost, so a program that passes is_valid can still be wrong. Compare the list of keys with the list you expect after each operation.
Removing the successor by key when keys repeat. When a node has two children, the delete copies the smallest key from its right subtree and then deletes that key from the right subtree. If the tree can hold repeated keys, the search for that key can find a different node with the same value. A tree that stores each key once, like the fixed program, avoids this.
Practice
Exercise 1. Insert 4, 2 and 6 into a new buggy tree, in that order. What does contains(2) return?
Show the answer
It returns false. The root is 4. The first test, key > cur->key, is 2 greater than 4, which is false. So the code checks the next test, key < cur->key. Two is less than 4, so the code moves to the right child, 6. Two is less than 6, so the code moves to the right child of 6, which is empty. The loop stops and returns false. The correct answer is true, because 2 was inserted. The comparisons are reversed, as in bug 2.
Exercise 2. The fixed insert does not add a duplicate. Insert 5, then 5 again, then 5 again. What do size() and keys() print?
Show the answer
size() prints 1 and keys() prints the single value 5. The first insert creates the node and sets added. The second and third inserts find the key already present, so insert_into returns the node unchanged and added stays false. The size stays at 1.
Exercise 3. Node 2 has only a left child, node 1, and no right child. Which line of the fixed erase_from handles this node, and what does it return?
Show the answer
The line is if (!node->right) { return std::move(node->left); }. It returns the subtree rooted at 1, so node 1 takes the place of node 2 in the tree. The buggy version had this line too, so the left-only case was never the source of bug 3. Bug 3 was in the branch for a missing left child.
Exercise 4. The fixed erase never lowers size_. Change erase so that the size goes down by one when the key is present, and stays the same when the key is absent.
Show the answer
Check with contains before the delete:
void erase(int key) {
if (contains(key)) {
root_ = erase_from(std::move(root_), key);
--size_;
}
}The check runs first, so the size changes only when the key is in the tree. Without the check, erasing a missing key would lower the size even though the tree did not change.
Exercise 5. Describe a test that would catch bug 3 without using is_valid. Give the input, the expected output and the comparison.
Show the answer
Insert 5, 3, 8 and 9 in that order, then erase 8. The expected keys are 3, 5 and 9. Compare the output of keys() with that list. The buggy program prints 3 and 5, so the comparison fails. The test must not depend on is_valid, because the tree that lost a key still passes that check.
Exercise 6. Use the fixed program with the tree from the two-child section: insert 5, 3, 8, 2, 4 and 9, then erase 3 instead of 5. What does keys() print?
Show the answer
It prints keys: 2 4 5 8 9. Node 3 has two children, so the delete copies the smallest key in its right subtree, which is 4, into the node. Then it deletes the old node 4, which is a leaf, so that call returns nullptr. The tree is now 5 at the root, with 4 on the left and 2 under 4, and 8 on the right with 9 under it. The keys in order are 2, 4, 5, 8 and 9.
Summary
- Write the expected value before you read the code, and compare it with the output.
- Print the keys in the tree. A sorted list of keys shows problems that a single true or false answer hides.
- The order check finds duplicates and reversed comparisons, but it cannot find a lost key.
- Trace one small example through the failing branch by hand before you change the code.
- Change one thing at a time, then run the same checks again.