Binary search trees: one path down

Binary search finds one key among a million sorted ones in at most 20 probes. Keeping those keys sorted is the expensive part: an array has to shift every key after the insertion point to make room, half a million moves for a key that lands in the middle (the arrays lesson counts them).

A binary search tree keeps sorted keys in nodes joined by links instead of side by side. Each node holds one key, smaller keys go in its left subtree and larger ones in its right, and the same holds at every node below. Finding a key is binary search again, one comparison per level, and adding one hangs a new node at the bottom without moving anything else. The catch is the shape: the same seven keys can make a tree 3 levels tall or a chain of 7, and only the order they arrived in decides which.

root, child and leaf

The root is the node at the top. Every node has at most two children, a left one and a right one, and a leaf is a node with none.

subtree

A node together with everything below it. A node's left subtree is its left child and all of that child's descendants, however deep.

search-tree rule

For every node, every key in its left subtree is smaller than the node's key and every key in its right subtree is larger. Each key is stored once.

height and depth

Height is the number of levels, counting the root's level as 1: the seven-key tree below has height 3. A node's depth counts the steps down from the root, which has depth 0. (Some books count height in steps instead, which gives one fewer.)

in-order successor

The next larger key in the tree. When a node has a right subtree, its successor is the smallest key there: go right once, then left as far as possible.

This tree holds seven keys. 50 is the root, 30 and 70 are its children, and 20, 40, 60 and 80 are leaves. Search for a key and watch the path: at each node the search compares, then goes left or right.

When the search for 40 goes left at 50, it rules out 50's whole right subtree, 70, 60 and 80, without looking at them: every key there is larger than 50, so none of them can be 40. That is binary search again. The subtree the search is in plays the part of the window, and each comparison throws away everything else. In this tree the root, 50, is even the middle key, just as binary search probes the middle first.

Insert is a search that is meant to fail. Where the walk falls off the tree is the only place the new key keeps the rule, so it becomes a new leaf there, and no other node moves. Inserting a key the tree already holds changes nothing.

A tree with every level full holds 1, 3, 7, 15 … keys in 1, 2, 3, 4 … levels: $2^h - 1$ keys in h levels. So n keys can fit in about $\log_2 n$ levels, 20 for a million, the same count as binary search's probes. But the shape is decided by the order the keys arrive in.

A chain has height n, so search, insert and delete all cost O(n), no faster than checking a list from the front. Keys that arrive in random order usually make a tree of height O(log n), a small multiple of $\log_2 n$, but real data often arrives sorted or nearly sorted: IDs, timestamps, names read from a sorted file. Self-balancing trees fix that by reshaping the tree as keys come and go, so the height stays O(log n) whatever the order.

Before each comparison, predict which way the walk goes. Insert 45, then 55: each walk asks at every node it passes. Then try inserting 50, a key the tree already has.

In code, a node is a small object: a key and two links, None (null in JavaScript) where there is no child. insert(node, key) is recursive, like the functions in the recursion lesson: it adds the key somewhere below node and returns the root of that subtree. A call on an empty subtree returns a brand-new node, and every caller stores what comes back as its child. search changes no links, so it never has to come back up the path, and a loop is enough: it moves node to a child until it finds the key or runs out of tree.

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 search(node, key):
    while node is not None:
        if key == node.key:
            return True
        if key < node.key:
            node = node.left
        else:
            node = node.right
    return False

root = None
for key in [50, 30, 70, 40]:
    root = insert(root, key)
print(search(root, 40))
print(search(root, 60))

The rule also hands you the keys in sorted order. An in-order traversal lists a node's left subtree, then the node, then its right subtree, recursively. Everything on the left is smaller and everything on the right is larger, so if each subtree comes out sorted, so does the whole list, and each subtree does, by the same argument one level down.

Listing all n keys this way takes O(n). The smallest key is the leftmost node (keep going left until there is no left child) and the largest is the rightmost, each O(h) away. That is what a search tree offers over a hash table: the keys in order, the smallest and largest, and every key between two values.

Deleting depends on how many children the node has. A leaf is simply removed. A node with one child is replaced by that child, which brings its whole subtree up with it; every key there was already on the correct side of everything above. A node with two children leaves two subtrees and only one slot, so the node stays and gets a new key instead: its in-order successor, the next larger key. Go right once, then left as far as possible. That key is larger than everything in the left subtree and smaller than everything else in the right, so the rule still holds. The successor never has a left child (that child would be smaller still), so taking it out of its old place is one of the two easy cases.

Each delete is one walk down to the node, and with two children a little further, to the successor: O(h) again. Using the in-order predecessor instead, the largest key in the left subtree, works just as well; this visualiser uses the successor.

• A binary search tree keeps every key in a node's left subtree smaller and every key in its right subtree larger, for whole subtrees, not just a node's children.
• Search, insert and delete follow one path down from the root, so they cost O(h). Insert adds a new leaf where a search for the key falls off the tree; nothing else moves.
• h is about log₂ n when the tree is balanced (20 levels for a million keys), but n when keys arrive sorted and the tree becomes a chain: then every operation is O(n).
• An in-order traversal (left subtree, node, right subtree) visits the keys in sorted order in O(n). The smallest key is the leftmost node and the largest the rightmost.
• Deleting a node with two children copies in its in-order successor (right once, then left as far as possible) and removes the successor's old node, which has at most one child.
• Next: self-balancing trees, which reshape themselves to keep h O(log n) whatever the order; try sorted inserts on the AVL tree. Practise with Check a Binary Search Tree, Kth Smallest Value in a Binary Search Tree and Lowest Common Ancestor in a Binary Search Tree, write Insert into a binary search tree and Write an inorder traversal yourself, or open the binary search tree visualiser to try more operations.