Binary Search Trees

What is a binary search tree?

A binary search tree (BST) is a binary tree with one rule, applied at every node:

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80
        /
      35

That single rule makes searching fast. To find 60, start at the root: 60 is bigger than 50, so it can only be on the right. 60 is smaller than 70, so go left, and there it is. Each comparison throws away an entire subtree, just like binary search on a sorted array. The difference is that a BST also lets you insert and delete without shifting anything.

The rule also means an in-order traversal (left, node, right) visits the keys in sorted order: 20 30 35 40 50 60 70 80.

How it works

Insert follows exactly the same path as a search. When it falls off the tree (reaches null), that empty spot is where the new key belongs.

Delete has three cases, depending on how many children the node has:

1. No children (a leaf): just remove it.
2. One child: replace the node with its child. The child's whole subtree moves up one level and still obeys the rule.
3. Two children: find the in-order successor, the smallest key in the right subtree (go right once, then left as far as possible). Copy its key into the node, then delete the successor from the right subtree. The successor has no left child, so that second delete is always case 1 or 2.

Operations and their cost

Every operation walks one path from the root, so it costs O(height). The height is about log₂ n when the tree is balanced, but if you insert keys that are already sorted, every new key goes to the right of the last one and the tree becomes a chain of height n. The last line of the program below shows exactly that.

Building one yourself

The implementation uses recursion for insert and delete: each call returns the (possibly new) root of its subtree, and the parent stores it in left or right. That one pattern handles inserting into an empty tree and deleting the root without any special cases.

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


class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        return node  # equal keys are ignored: a BST stores each key once

    def contains(self, key):
        node = self.root
        while node is not None:
            if key == node.key:
                return True
            node = node.left if key < node.key else node.right  # discard half the tree
        return False

    def minimum(self):
        node = self.root
        while node.left is not None:
            node = node.left
        return node.key

    def maximum(self):
        node = self.root
        while node.right is not None:
            node = node.right
        return node.key

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return None
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        else:
            if node.left is None:        # no children, or only a right child
                return node.right
            if node.right is None:       # only a left child
                return node.left
            successor = node.right       # two children: copy the next larger key here,
            while successor.left is not None:
                successor = successor.left
            node.key = successor.key     # then delete that key from the right subtree
            node.right = self._delete(node.right, successor.key)
        return node

    def inorder(self):
        out = []

        def walk(node):
            if node is not None:
                walk(node.left)
                out.append(node.key)
                walk(node.right)

        walk(self.root)
        return out

    def height(self):
        def h(node):
            return 0 if node is None else 1 + max(h(node.left), h(node.right))

        return h(self.root)


def yes_no(flag):
    return "true" if flag else "false"


def joined(values):
    return " ".join(str(v) for v in values)


tree = BST()
for key in (50, 30, 70, 20, 40, 60, 80, 35):
    tree.insert(key)
print("in-order (sorted):", joined(tree.inorder()))
print("height:", tree.height())
print("contains 60:", yes_no(tree.contains(60)))
print("contains 65:", yes_no(tree.contains(65)))
print(f"min: {tree.minimum()}, max: {tree.maximum()}")
tree.delete(20)
print("delete 20 (leaf):", joined(tree.inorder()))
tree.delete(30)
print("delete 30 (one child):", joined(tree.inorder()))
tree.delete(50)
print("delete 50 (two children, the root):", joined(tree.inorder()), "| new root:", tree.root.key)

chain = BST()
for key in (1, 2, 3, 4, 5):
    chain.insert(key)
print("inserting 1..5 in order gives height", chain.height())

in-order (sorted): 20 30 35 40 50 60 70 80
height: 4
contains 60: true
contains 65: false
min: 20, max: 80
delete 20 (leaf): 30 35 40 50 60 70 80
delete 30 (one child): 35 40 50 60 70 80
delete 50 (two children, the root): 35 40 60 70 80 | new root: 60
inserting 1..5 in order gives height 5

Keeping it balanced

Real-world sorted collections never use a plain BST, because of the sorted-input problem. They use self-balancing trees, which do a few extra pointer rotations after inserts and deletes to keep the height O(log n) no matter what order the keys arrive in:

• AVL trees keep the two subtrees of every node within one level of each other's height.
• Red-black trees use a colouring rule that keeps the longest path at most twice the shortest. Java's TreeMap and C++'s std::map are red-black trees.

You rarely need to write a balanced tree yourself, but you should know that's why the library versions guarantee O(log n).

BSTs in the standard libraries

BST or hash map?

Both store keys. A hash map is faster for plain lookups (O(1) on average), so it is the default. Choose a BST (a sorted map) when order matters: listing keys in sorted order, finding the smallest key greater than x, or counting keys in a range. Those questions take O(log n) in a balanced BST and O(n) in a hash map.

Common mistakes

• Checking only parent and child. A tree where every node is larger than its left child can still break the rule further down. The lab problem Validate a Binary Search Tree is built around this trap: pass the allowed range down the tree.
• Forgetting duplicates. Decide whether to ignore them (as here), count them, or always send them one way.
• Losing the subtree on delete. In the one-child case, the parent must point at the child, not at null.
• Assuming O(log n) for a tree that isn't balanced.

When to use a BST

Use a balanced BST (through your language's sorted map or set) when you need a collection that stays sorted while you insert and delete, or when you need range queries, floor/ceiling lookups or the k-th smallest item. Write one by hand when learning, and in interviews, where they are a favourite topic.