Practical 5: the Binary Search Tree, Create, Insert and Search

Creating a tree and inserting into it

from bst import BinarySearchTree

tree = BinarySearchTree()
print("empty tree: len", len(tree), " height", tree.height(),
      " valid", tree.is_valid())

print()
print("inserting 50, 30, 70, 20, 40, 60, 80:")
for key in [50, 30, 70, 20, 40, 60, 80]:
    comparisons = tree.insert(key)
    print(f"  insert {key:>3}  {comparisons} comparison(s)  "
          f"len now {len(tree)}, height {tree.height()}")

print()
print("the tree, on its side with the root at the left:")
print(tree.draw())
print()
print("in-order (which must be sorted):", tree.in_order())
print("is it a valid BST?              ", tree.is_valid())
print("minimum", tree.minimum(), " maximum", tree.maximum(),
      " height", tree.height(), " nodes", len(tree))

empty tree: len 0  height -1  valid True

inserting 50, 30, 70, 20, 40, 60, 80:
  insert  50  0 comparison(s)  len now 1, height 0
  insert  30  1 comparison(s)  len now 2, height 1
  insert  70  1 comparison(s)  len now 3, height 1
  insert  20  2 comparison(s)  len now 4, height 2
  insert  40  2 comparison(s)  len now 5, height 2
  insert  60  2 comparison(s)  len now 6, height 2
  insert  80  2 comparison(s)  len now 7, height 2

the tree, on its side with the root at the left:
        80
    70
        60
50
        40
    30
        20

in-order (which must be sorted): [20, 30, 40, 50, 60, 70, 80]
is it a valid BST?               True
minimum 20  maximum 80  height 2  nodes 7

Read the drawing sideways: turn your head to the left and the root is at the top. The in-order walk comes out sorted, and that is the test that the tree really is a binary search tree, because the in-order walk of a BST is always the keys in order.

Duplicates are a decision, not an accident

from bst import BinarySearchTree

tree = BinarySearchTree([50, 30, 70])
print("before        ", tree.in_order(), " len", len(tree))

result = tree.insert(30)
print("insert 30 again returned", result,
      "which this class uses to mean 'already there'")
print("after         ", tree.in_order(), " len", len(tree))
print("so the tree holds a SET of keys, with no duplicates")

before         [30, 50, 70]  len 3
insert 30 again returned -1 which this class uses to mean 'already there'
after          [30, 50, 70]  len 3
so the tree holds a SET of keys, with no duplicates

There are three defensible things to do with a duplicate key and you must say which you chose:

The one wrong answer is to have no rule, so that equal keys sometimes go left and sometimes right. Then search can fail to find a key that is in the tree, because it looks down only one side.

Searching, with the path shown

from bst import BinarySearchTree

tree = BinarySearchTree([50, 30, 70, 20, 40, 60, 80])
print("the tree holds", tree.in_order())
print(f"  {'key':>5} {'found':>7} {'comparisons':>13}  the path taken")
for key in [50, 20, 80, 40, 45, 5, 100]:
    found, comparisons, path = tree.search(key)
    trail = " -> ".join(str(k) for k in path)
    print(f"  {key:>5} {found!s:>7} {comparisons:>13}  {trail}")

print()
print("7 nodes, and no search took more than 3 comparisons,")
print("because each comparison discards a whole subtree")
print()
print("the in operator works too:", 40 in tree, 45 in tree)

the tree holds [20, 30, 40, 50, 60, 70, 80]
    key   found   comparisons  the path taken
     50    True             1  50
     20    True             3  50 -> 30 -> 20
     80    True             3  50 -> 70 -> 80
     40    True             3  50 -> 30 -> 40
     45   False             3  50 -> 30 -> 40
      5   False             3  50 -> 30 -> 20
    100   False             3  50 -> 70 -> 80

7 nodes, and no search took more than 3 comparisons,
because each comparison discards a whole subtree

the in operator works too: True False

Read the path column. Every search walks down one route from the root and never backtracks, and the longest route is the height of the tree plus one. A search costs at most height + 1 comparisons, which is the whole reason a tree is used.

Notice that a failed search is not free: looking for 45 still walked three nodes before running out of tree. A failed search costs the same as the deepest successful one on that route.

The defect: sorted input

This is the question an examiner asks, and the answer is a measurement.

from bst import BinarySearchTree

keys = [10, 20, 30, 40, 50, 60, 70]

balanced = BinarySearchTree([40, 20, 60, 10, 30, 50, 70])
degenerate = BinarySearchTree(keys)

print("inserted in a good order: 40, 20, 60, 10, 30, 50, 70")
print(balanced.draw())
print(f"  height {balanced.height()}, in-order {balanced.in_order()}")
print()
print("inserted in SORTED order: 10, 20, 30, 40, 50, 60, 70")
print(degenerate.draw())
print(f"  height {degenerate.height()}, in-order {degenerate.in_order()}")
print()
print("both are valid binary search trees:",
      balanced.is_valid(), degenerate.is_valid())
print("both hold the same keys in the same order.")
print("but one is a tree and the other is a linked list.")

inserted in a good order: 40, 20, 60, 10, 30, 50, 70
        70
    60
        50
40
        30
    20
        10
  height 2, in-order [10, 20, 30, 40, 50, 60, 70]

inserted in SORTED order: 10, 20, 30, 40, 50, 60, 70
                        70
                    60
                50
            40
        30
    20
10
  height 6, in-order [10, 20, 30, 40, 50, 60, 70]

both are valid binary search trees: True True
both hold the same keys in the same order.
but one is a tree and the other is a linked list.

The second tree has every node as the right child of the one before it. It is a linked list wearing a tree's class, and every left pointer in it is None.

from bst import BinarySearchTree

print(f"{'n':>6} {'balanced height':>17} {'sorted height':>15} "
      f"{'worst search, balanced':>24} {'worst search, sorted':>22}")


def balanced_order(keys):
    """Insert the middle first, then each half, so the tree comes out balanced."""
    if not keys:
        return []
    middle = len(keys) // 2
    return ([keys[middle]] + balanced_order(keys[:middle])
            + balanced_order(keys[middle + 1:]))


for n in [7, 15, 31, 63, 127]:
    keys = list(range(1, n + 1))
    good = BinarySearchTree(balanced_order(keys))
    bad = BinarySearchTree(keys)
    _, good_worst, _ = good.search(n)
    _, bad_worst, _ = bad.search(n)
    print(f"{n:>6} {good.height():>17} {bad.height():>15} "
          f"{good_worst:>24} {bad_worst:>22}")

print()
print("the balanced height grows by 1 when n roughly doubles, which is log n.")
print("the sorted height is n - 1, and the worst search is n, which is a linked list.")

     n   balanced height   sorted height   worst search, balanced   worst search, sorted
     7                 2               6                        3                      7
    15                 3              14                        4                     15
    31                 4              30                        5                     31
    63                 5              62                        6                     63
   127                 6             126                        7                    127

the balanced height grows by 1 when n roughly doubles, which is log n.
the sorted height is n - 1, and the worst search is n, which is a linked list.

There it is in numbers. A balanced tree of 127 keys has a height of 6 and the worst search takes 7 comparisons. The same keys inserted in sorted order give a height of 126 and a worst search of 127. Same keys, same class, same rule satisfied, and a structure that is twenty times worse.

So the honest statement of a BST's cost is: O(log n) if it is balanced, O(n) if it is not, and nothing in the plain insertion keeps it balanced. The structures that do, AVL trees and red-black trees, rebalance on every insertion, and they are the next thing to read about after this paper.

A practical cure needs no new structure at all: shuffle the keys before inserting them, or insert the middle key first as balanced_order above does.

Checking the rule properly

from bst import BinarySearchTree


class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right


def children_only(node):
    """The WRONG check: it looks at immediate children only."""
    if node is None:
        return True
    if node.left is not None and node.left.key >= node.key:
        return False
    if node.right is not None and node.right.key <= node.key:
        return False
    return children_only(node.left) and children_only(node.right)


def with_bounds(node, low=None, high=None):
    """The right check: every DESCENDANT must be inside the bounds."""
    if node is None:
        return True
    if low is not None and node.key <= low:
        return False
    if high is not None and node.key >= high:
        return False
    return (with_bounds(node.left, low, node.key)
            and with_bounds(node.right, node.key, high))


#        10
#       /  \
#      5    15
#          /  \
#         6    20      <- 6 is less than 10 but sits in 10's RIGHT subtree
broken = Node(10, Node(5), Node(15, Node(6), Node(20)))

print("the children-only check says it is a BST :", children_only(broken))
print("the bounds check says it is a BST        :", with_bounds(broken))
print()
print("and the consequence: searching for 6 from the root")
here, path = broken, []
while here is not None:
    path.append(here.key)
    if here.key == 6:
        break
    here = here.left if 6 < here.key else here.right
print("  the path taken:", " -> ".join(str(k) for k in path))
print("  found?", here is not None, "although 6 IS in the tree")

the children-only check says it is a BST : True
the bounds check says it is a BST        : False

and the consequence: searching for 6 from the root
  the path taken: 10 -> 5
  found? False although 6 IS in the tree

There is why the rule says subtree and not child. Node 6 is a legal left child of 15, and 15 is a legal right child of 10, and yet 6 is smaller than 10 and sits to its right. The children-only check passes it. And the consequence is fatal: searching for 6 goes left at the root and never finds it.

Deletion, which MU does not ask for and an examiner might

MU's three bullets are create, insert and search. Deletion has three cases and is worth knowing.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node


def smallest(node):
    while node.left is not None:
        node = node.left
    return node


def delete(node, key):
    if node is None:
        return None, "not found"
    if key < node.key:
        node.left, why = delete(node.left, key)
        return node, why
    if key > node.key:
        node.right, why = delete(node.right, key)
        return node, why
    # found it. Three cases.
    if node.left is None and node.right is None:
        return None, "a leaf: just remove it"
    if node.left is None:
        return node.right, "one child: the child takes its place"
    if node.right is None:
        return node.left, "one child: the child takes its place"
    successor = smallest(node.right)
    node.key = successor.key
    node.right, _ = delete(node.right, successor.key)
    return node, "two children: the in-order successor takes its key"


def in_order(node):
    if node is None:
        return []
    return in_order(node.left) + [node.key] + in_order(node.right)


root = None
for key in [50, 30, 70, 20, 40, 60, 80, 65]:
    root = insert(root, key)
print("start      ", in_order(root))

for key in [20, 70, 50, 99]:
    root, why = delete(root, key)
    print(f"delete {key:>3}  {str(in_order(root)):<38} {why}")

start       [20, 30, 40, 50, 60, 65, 70, 80]
delete  20  [30, 40, 50, 60, 65, 70, 80]           a leaf: just remove it
delete  70  [30, 40, 50, 60, 65, 80]               two children: the in-order successor takes its key
delete  50  [30, 40, 60, 65, 80]                   two children: the in-order successor takes its key
delete  99  [30, 40, 60, 65, 80]                   not found

The in-order successor is the smallest key in the right subtree, which is the next key in sorted order. It is chosen because it is the only key that can sit where the deleted one was without breaking the rule: everything left of the node is smaller than it, and everything else right of it is larger. Note that the in-order output stays sorted after every deletion, which is the check.

Procedure

1. Save bst.py with Node holding key, left and right, and BinarySearchTree holding root

and count.

1. Write insert iteratively, walking left for a smaller key and right for a larger one, and decide what to do with a duplicate.
2. Write search returning whether it was found, how many comparisons it took, and the path.
3. Write minimum (leftmost), maximum (rightmost), height and in_order.
4. Write is_valid with bounds, not children, and draw to print the tree sideways.
5. Insert 50, 30, 70, 20, 40, 60, 80 and print the drawing, the in-order walk and the height.
6. Confirm the in-order walk is sorted, which is the proof that it is a BST.
7. Search for several keys present and absent, printing the path and the comparisons for each.
8. Build the same keys in sorted order and print the height of both trees.
9. Tabulate the height and worst search for n of 7 to 127, balanced against sorted.

Result

The tree of seven keys had a height of 2 and no search took more than 3 comparisons. The in-order walk was sorted at every stage and is_valid was True. A duplicate insertion returned the marker and left the tree unchanged. Searching printed the path taken, which went down one route without backtracking, and a failed search cost as much as the deepest successful one on that route. The same seven keys inserted in sorted order gave a height of 6 rather than 2, with every left pointer None, and both trees were valid and held the same keys. Across n of 7 to 127 the balanced height grew by one as n roughly doubled, while the sorted height was n - 1 and the worst search n: at n of 127, height 6 and 7 comparisons against height 126 and 127 comparisons. The children-only validity check passed a tree in which a key smaller than the root sat in its right subtree, and a search for that key then failed although it was present.

Where marks are lost

• Checking only the immediate children for the BST rule. It is every descendant.
• No rule for duplicates, so equal keys go both ways and search can miss one that is there.
• Not printing the in-order walk. A sorted in-order walk is the proof that it is a BST.
• Not counting the comparisons, so the O(log n) claim is asserted rather than shown.
• Saying a BST is O(log n) without the word balanced. On sorted input it is O(n).
• Not trying sorted input at all. It is the examiner's question.
• An empty tree with no case for it: the first insertion sets the root, and minimum on an empty

tree must raise.

• height of an empty tree given as 0. It is -1 by the usual definition; one node is 0. Say which

you used.

For the journal

The aim in MU's words, all three bullets. The tree picture with the root, a parent, a child and a leaf labelled, and the BST rule written out with the word subtree underlined. bst.py in full. Then the insertion run with the comparison count and the height after each key, the drawing, and the in-order walk shown to be sorted, which is the proof. Then the search table with the path and the comparisons for keys present and absent. Then the sorted input tree drawn beside the balanced one, and the table of heights for n of 7 to 127. One sentence on duplicates, saying which of the three treatments you chose. The conclusion: one comparison at a node discards a whole subtree, so a search costs at most the height plus one, which is about log n when the tree is balanced and n when the keys arrived in order.

Quick revision

• root no parent, leaf no children, depth of a node from the root at 0, height the

deepest depth. Empty tree height -1, one node 0.

• Binary means at most two children.
• BST rule: everything in the left SUBTREE is smaller, everything in the right SUBTREE is larger.

Subtree, not child.

• Insert: walk left for smaller and right for larger until a None, and put the node there.
• Search: one comparison discards a whole subtree. At most height + 1 comparisons.
• The in-order walk of a BST is sorted. That is the test.
• minimum is the leftmost node, maximum the rightmost. No searching needed.
• Duplicates: refuse, count, or always one side. Decide, and say which.
• Sorted input gives a degenerate tree: height n - 1, search O(n), every left pointer None.
• Measured: 127 keys give height 6 and 7 comparisons balanced, against height 126 and 127 sorted.
• The cure is to shuffle the keys, insert the middle first, or use a self balancing tree (AVL,

red-black).

• Validity is checked with bounds passed down, not by comparing children.
• Deletion: a leaf goes; one child takes its place; two children means copy the in-order successor

(the smallest in the right subtree) and delete it.

Questions you should be able to answer

1. State the binary search tree rule. Every key in a node's left subtree is smaller than the node, and every key in its right subtree is larger.

2. Why does it say subtree rather than child? Because a key can be a legal child of its parent and still be on the wrong side of an ancestor. This chapter shows one: 6 as the left child of 15 under a root of 10. The search then goes left at the root and never finds it.

3. How do you prove a tree is a BST? Walk it in order; the keys come out sorted. Or check it with bounds passed down the recursion.

4. How many comparisons does a search cost, at most? The height of the tree plus one, because each comparison moves down exactly one level.

5. Where is the smallest key? The leftmost node: follow left until it is None. No comparisons with anything else are needed.

6. What happens if you insert keys in sorted order? Every node becomes the right child of the one before, so the tree is a linked list with height n - 1 and search O(n).

7. Give the measured figures for that. For 127 keys: balanced gives height 6 and a worst search of 7; sorted gives height 126 and a worst search of 127.

8. So what is the honest cost of a BST search? O(log n) when the tree is balanced and O(n) when it is not, and plain insertion does nothing to keep it balanced.

9. Name two cures. Shuffle the keys before inserting, or insert the middle key first and recurse on the halves. For a tree that stays balanced under any input, use an AVL or a red-black tree.

10. What are the three cases of deletion? A leaf is simply removed; a node with one child is replaced by that child; a node with two children takes the key of its in-order successor, the smallest key in its right subtree, which is then deleted.

11. Why the in-order successor and not any other key? Because it is the only key that can sit in that position without breaking the rule: it is larger than everything on the left and smaller than everything remaining on the right.