Why this matters
Most binary search tree bugs do not crash the program. The tree keeps running and gives wrong answers. A search returns False for a key that is present. A size counter says 4 when the tree holds 5 keys. A delete quietly removes a whole part of the tree. These bugs are easy to miss when you only read the code, so this lesson practises a method that finds them with evidence.
The method has four steps. Read the code and predict what it prints. Run it, and compare the output with a second, trusted answer. Find the first line where the two disagree. Fix one bug, run again, and repeat.
The trusted answer comes from a Python set. A set keeps distinct values, and sorting its contents gives the sorted list a tree should print. Using it as an answer key is called using an oracle. The tree under test and the oracle get the same operations, and their results are printed side by side.
The program uses the insert, search and delete code from the earlier lessons in this module. It does not balance the tree. The AVL and red-black lessons cover balancing.
The lab program
The program below has a tree class called BuggyBst. The class has four methods: insert, contains, delete and inorder. The inorder method lists the keys from smallest to biggest, which is the first thing to check when a BST looks wrong. Each class method keeps a size count, which should equal the number of keys in the tree.
The program runs three scenarios. Scenario A inserts a duplicate key and then searches for a key. Scenario B deletes a node that has only one child. Scenario C deletes a node that has two children. Each scenario prints the tree's answer and the oracle's answer.
Before you run it, read the code and predict the three outputs. Then run it.
The output is:
A: after inserts 50, 70, 80, 1000, 50
tree inorder: [50, 50, 70, 80, 1000]
oracle: [50, 70, 80, 1000]
tree size: 5, oracle size: 4
A: contains 1000: tree False , oracle True
B: after delete 70 (only a right child)
tree inorder: [50]
oracle: [50, 80]
tree size: 2, oracle size: 2
C: after delete 40 (two children)
tree inorder: [20, 50, 50, 60, 70]
oracle: [20, 50, 60, 70]
tree size: 4, oracle size: 4Every scenario disagrees with the oracle. The rest of the lesson takes them one at a time.
The keys in scenario A that equal 1000 are made with int("1000"). That call builds a new number object at run time, so it is not the same object as any other 1000 in the program. The reason for this is explained in the second bug below.
Scenario A: duplicates and an identity check
Look at the first two lines of scenario A. The tree's inorder list has 50 twice. The oracle has it once. The tree's size is 5, and the oracle's size is 4. Two different bugs cause this.
Bug 1 is in insert. The method adds a new node every time it is called, even when the key is already in the tree. It also increases size on every call, before it checks anything. The first 50 becomes the root. The second 50 is not smaller than 50, so the code takes the else branch and goes right. It then goes left from 70 and stores a second node holding 50. The tree now has two nodes with the same key.
A set should not hold duplicates. The fix is to stop when the key is already there, and to count only the nodes that are really added. The fixed version later in this lesson does both.
Bug 2 is in contains. The line if cur.key is key: looks like a normal comparison. It is not. The is operator asks whether two names point at the same object, not whether the numbers are equal. CPython, the usual Python program, keeps one shared object for each small integer, from -5 to 256, so is seems to work for small numbers. A number built at run time, such as the 1000 from int("1000"), is a separate object. So is returns False for that number, even though the numbers are equal.
Here is a small program that shows the difference. It is separate from the lab, and it is worth running once.
a = int("127")
b = int("127")
c = int("1000")
d = int("1000")
print("127 is 127:", a is b)
print("1000 is 1000:", c is d)
print("1000 == 1000:", c == d)Its output is:
127 is 127: True
1000 is 1000: False
1000 == 1000: TrueThe rule for numbers is simple. Use == to compare values, and is only for None. The fixed contains uses ==, which compares the numbers.
In Python, the only way to hit this bug is to write is where you meant ==.
Scenario B: a delete that drops a subtree
In scenario B the tree holds 50, 70 and 80. Node 70 has only one child, which is 80 on its right. The tree's inorder list after the delete is [50], and the oracle has [50, 80]. The key 80 has vanished from the walk, but the size still says 2.
The bug is in the line if n.left is None or n.right is None: return n.left. The code means to handle a node with at most one child. It returns the left child in every case. When the node has only a right child, the left child is None, so _delete returns None. Whatever hangs under the right child is cut off from the tree, and the whole right subtree is lost.
The size counter disagrees with the walk. The counter goes from 3 to 2 correctly, because one key was removed. The walk shows only one key left, because the key 80 was lost with the subtree. Two numbers that should match do not. When you see a mismatch like this, look for a node that was removed without its children being moved.
The fix is to return whichever child is not None. If the left child is None, return the right child. If the right child is None, return the left child.
Scenario C: a delete that leaves a copy behind
Scenario C deletes 40 from a tree whose root has two children. The code is correct to find the smallest key in the right subtree, which is 50 (the successor, the next key in sorted order), and to copy it into the root. The bug is what comes next. It does not remove the old node for 50 from the right subtree. After the delete, 50 is in the tree twice, once at the root and once below it. The walk shows [20, 50, 50, 60, 70], and the size is 4.
The fix is to delete the successor from the right subtree after copying it. Calling _delete on the right subtree with the successor's key does that, because the successor has no left child, so the call takes the one-child path (fixed in scenario B) and removes it.
The first fix for scenario C was wrong, and the oracle caught it. The next section shows the mistake.
Fixing the bugs one at a time
The fixes below change three methods. insert gets the duplicate check and counts only real additions. contains uses ==. The private _delete handles the one-child case by returning the child that exists, and the two-child case by deleting the successor from the right subtree. The rest of the program stays the same.
The fixed class below replaces the three methods. It keeps show and the three scenarios from the lab, and it runs them on the fixed class.
from lab import Node, BuggyBst, show
class FixedBst(BuggyBst):
def insert(self, key):
if self.root is None:
self.root = Node(key)
self.size += 1
return
cur = self.root
while True:
if key == cur.key:
return
if key < cur.key:
if cur.left is None:
cur.left = Node(key)
self.size += 1
return
cur = cur.left
else:
if cur.right is None:
cur.right = Node(key)
self.size += 1
return
cur = cur.right
def contains(self, key):
cur = self.root
while cur is not None:
if key == cur.key:
return True
cur = cur.left if key < cur.key else cur.right
return False
def _delete(self, n, key):
if n is None:
return None
if key < n.key:
n.left = self._delete(n.left, key)
return n
if key > n.key:
n.right = self._delete(n.right, key)
return n
if n.left is None:
self.size -= 1
return n.right
if n.right is None:
self.size -= 1
return n.left
succ = n.right
while succ.left is not None:
succ = succ.left
n.key = succ.key
n.right = self._delete(n.right, succ.key)
return nThe import line expects the Node, BuggyBst and show definitions from the lab program, saved as lab.py in the same folder. Importing lab.py also runs the lab's three scenarios, so the lab's output prints first. Below the class, in the same file, add the three scenarios with FixedBst in place of BuggyBst:
a = FixedBst()
oa = set()
for k in [50, 70, 80, int("1000"), 50]:
a.insert(k)
oa.add(k)
show("A: after inserts 50, 70, 80, 1000, 50", a, oa)
print("A: contains 1000: tree", a.contains(int("1000")), ", oracle", int("1000") in oa)
b = FixedBst()
ob = set()
for k in [50, 70, 80]:
b.insert(k)
ob.add(k)
b.delete(70)
ob.discard(70)
show("B: after delete 70 (only a right child)", b, ob)
c = FixedBst()
oc = set()
for k in [40, 20, 60, 50, 70]:
c.insert(k)
oc.add(k)
c.delete(40)
oc.discard(40)
show("C: after delete 40 (two children)", c, oc)The output of the fixed scenarios, after the lab's output, is:
A: after inserts 50, 70, 80, 1000, 50
tree inorder: [50, 70, 80, 1000]
oracle: [50, 70, 80, 1000]
tree size: 4, oracle size: 4
A: contains 1000: tree True , oracle True
B: after delete 70 (only a right child)
tree inorder: [50, 80]
oracle: [50, 80]
tree size: 2, oracle size: 2
C: after delete 40 (two children)
tree inorder: [20, 50, 60, 70]
oracle: [20, 50, 60, 70]
tree size: 4, oracle size: 4Every line now matches the oracle.
Notice where self.size -= 1 appears. It is written in the two branches that really remove a node, the ones where a node has at most one child. In the two-child case the node itself stays in the tree and only its key changes. The recursive call removes the successor and decrements the size once, for that removal. An earlier draft of this fix put self.size -= 1 at the top of the found-node branch, so the two-child case decremented the size twice. Scenario C of the lab caught it. The earlier draft printed this for scenario C:
C draft
tree inorder: [20, 50, 60, 70]
oracle: [20, 50, 60, 70]
tree size: 3, oracle size: 4The walk was right, and the size was one too small. The size is a second answer that must match, so the check compares both.
Common mistakes
Mistake one: comparing numbers with is. The symptom is a search that returns False for a key that was inserted, and it only happens for numbers outside the range -5 to 256 when the number was built at run time. The fix is ==.
Mistake two: writing the size change in the wrong place. The symptom is a size that is one too big or one too small after a delete, while the walk is correct. Check that the counter changes exactly once for each node removed from the tree.
Mistake three: forgetting that a delete must reconnect the children. If a node is removed and its children are not attached to the parent, the whole subtree disappears. The symptom is an inorder list that is shorter than the oracle.
Mistake four: reading a field of None after a delete. If you return the wrong node or forget a None check, Python stops the program with an error that names the type and the attribute. A search that finds no node can return None. Reading .key from that None gives an error like this:
AttributeError: 'NoneType' object has no attribute 'key'The message says that the code read the attribute key from a value that was None. The traceback above the message, the list of lines the program ran before it failed, shows the line where the read happens. The fix is to check for None before the read, or to find why the value was None.
Mistake five: a function that does not return on every path. Python does not check this before the program runs. When a path ends without a return, the function gives back None, and the caller may treat that as a value. For example, if contains ends its loop and has no return False after it, the call t.contains(5) gives None. In an if test, None counts as False, so the if still works, but a test such as print(t.contains(5)) shows None in the output. Add return False after the loop, so the answer is always a real True or False.
Mistake six: trusting one example. The three scenarios pass after the fix, but each one covers one bug. A tree with several operations in a row can fail in a new way. Add more scenarios, or write a loop that applies many inserts and deletes to the tree and to a set, and compares the two after each step.
Practice
Exercise 1. The tree is empty. Insert 5, then insert 5 again, using the buggy insert method from the lab. What does inorder print, and what is size?
Show the answer
The inorder list prints [5, 5], and size is 2. The buggy insert adds a node each time and counts each call. A set would print [5] and have size 1.
Exercise 2. In the buggy _delete, a node with only a left child is removed correctly, but a node with only a right child is not. Explain in two sentences why.
Show the answer
The buggy line returns n.left whenever either child is None. When the node has only a right child, n.left is None, so the method returns None and drops the right subtree.
Exercise 3. Write a Python expression that tests whether two variables x and y hold the same number, in a way that works for values such as 1000 built at run time. Then say why x is y is not reliable.
Show the answer
Use x == y. The is operator compares object identity. Small integers from -5 to 256 are shared objects in CPython, so is can seem to work for them, but a bigger number built at run time is a new object, and is returns False even when the numbers are equal.
Exercise 4. Using the oracle method, describe the test you would run to find a bug in a delete that only handles leaves. Which keys should the test use?
Show the answer
Insert a set of keys that includes nodes with one child and nodes with two children, then delete each of them in turn. After each delete, compare the inorder list and the size with a set that received the same operations. Leaves alone would pass, so the test must include inner nodes.
Exercise 5. Write a function same_as_oracle(tree, oracle) that returns True when the tree's inorder list equals the oracle's contents and the tree's size equals the oracle's size.
Show the answer
def same_as_oracle(tree, oracle):
return tree.inorder() == sorted(oracle) and tree.size == len(oracle)The function sorts the set to get a list in order, and compares it with the tree's inorder list. The == on two lists checks that both have the same items in the same order.
Summary
- Compare a tree's answers with a trusted answer key, such as a
set, and look at the first line that disagrees. - Compare numbers with
==, never withis, because two equal numbers built at run time can be different objects. - A delete must reconnect the surviving child, or the whole subtree is lost.
- For a node with two children, copy the successor's key and then delete the successor from the right subtree, so the key does not stay in two places.
- Update the size in the same branch where a node is removed, so it changes once per removal.