Binary search trees

What this chapter covers

A binary search tree is a binary tree with one rule that changes everything: for every node, all smaller values live in its left subtree and all larger ones in its right. That single invariant turns search, insert, and delete into the same motion — walk down from the root, comparing, until you find the value or the empty spot for it — and each step drops a level, so the work is the tree's height. When the tree is balanced that's O(log n), giving you an ordered container with fast everything: search, insert, delete, min, max, successor, and sorted iteration. This chapter builds it, watches it grow, and then confronts its fatal flaw — nothing here keeps it balanced — which is the entire reason the next two chapters exist.

A bit of history

The binary search tree was discovered independently several times around 1960 — P. F. Windley, Andrew Booth and Andrew Colin, and Thomas Hibbard all described versions within a couple of years, as the idea of a searchable ordered structure was clearly in the air once computers had enough memory to hold trees of pointers. Hibbard's 1962 paper gave the deletion algorithm this chapter uses, including the tricky two-child case. And almost immediately people noticed the problem: a BST built from sorted data degenerates into a linked list, so within a few years the search for a self-balancing tree began, producing the AVL tree (1962) and later the red-black tree — the next two chapters. So the BST arrived already knowing its own weakness, and the history of trees for the next decade was the history of fixing it.

The intuition

Everything a BST does is one idea: at each node, a comparison tells you which way to go. Searching for a value? Compare with the root — if smaller, the value can only be in the left subtree, so go left and forget the right entirely; if larger, go right. Repeat until you find it or run off the tree. Each comparison throws away a whole subtree, so the search is as deep as the tree is tall.

Inserting is the same walk, but when you run off the tree you plant the new node where you stopped — the empty spot you reached is exactly where that value belongs to keep the ordering intact. Deleting is the same walk to find the node, then a little surgery to close the gap without breaking the order (three cases, detailed below). And because the ordering rule holds everywhere, an in-order traversal — left, node, right — visits values from smallest to largest, so the tree hands you sorted output for free. That's the BST's whole value proposition over a hash table: a hash set answers "is it here?" faster, but it can't give you the minimum, the next-larger key, a range, or sorted order without scanning everything. The BST keeps the data ordered.

Complexity: how it scales

Every core operation — search, insert, delete, min, max — costs $O(h)$, the height of the tree. The whole game is what h is. If the tree is balanced, $h = O(\log n)$ and everything is fast. But nothing in this chapter's BST enforces balance, and the height depends entirely on insertion order. Insert random data and you get a roughly balanced tree, $O(\log n)$ deep. Insert sorted data and every node becomes the right child of the last — the tree degenerates into a linked list, $h = O(n)$, and every operation crawls. The balance chart shows this catastrophe directly:

Building an 8000-node tree from random data took about 11 ms; from sorted data it took 3090 ms — 291 times slower, because the sorted insertions built a degenerate tree and each insert walked the whole thing. Same values, same code, catastrophically different because of order. That is the problem balanced trees solve.

What it's good at, what it isn't

A balanced BST is the right structure whenever you need an ordered collection with fast updates: a map or set that also supports min, max, "next key after X," range queries, and sorted iteration. That's more than a hash table can do — hashing scatters keys, so it has no order — and it's what makes BSTs (in balanced form) the backbone of ordered maps in C++ (std::map), Java (TreeMap), and database indexes. When your queries are about order or ranges, not just membership, this is the family you want.

Its weaknesses are two. First, for pure membership with no ordered queries, a hash table's O(1) beats the BST's O(log n) — use a set unless you need the order. Second, and fatally for the plain BST, it doesn't stay balanced on its own, so adversarial or merely sorted input degrades it to O(n). The plain BST in this chapter is therefore a teaching structure: you'd never ship it, because the sorted-input case is too common and too catastrophic. What you ship is a self-balancing BST, which keeps the height O(log n) no matter the insertion order — the next two chapters.

The data, or the inputs

The face-off inserts random values into the BST, a sorted list, and a set, at growing sizes, to find where the BST's O(log n) insert overtakes the array's O(n) insert. The balance chart inserts the same number of values in random versus sorted order, isolating the degeneration. The animation inserts seven values into an empty tree so you can watch it take shape, each new node hung at the end of its search path.

Build it, one function at a time

Insert — walk down comparing, and hang the new node where you fall off the tree:

def insert(self, value, probe=None):
    """O(h): walk down comparing — left if smaller, right if larger — until you
    fall off the tree, then hang the new node there. Duplicates are ignored (a
    BST models a set). h is the height: log n balanced, n degenerate."""
    if self.search(value):
        if probe is not None:
            probe.append({"path": [], "new": value})
        return
    path = []
    self.root = self._insert(self.root, value, path)
    self._n += 1
    if probe is not None:
        probe.append({"path": path, "new": value})

def _insert(self, node, value, path):
    if node is None:
        return Node(value)
    path.append(node.value)
    if value < node.value:
        node.left = self._insert(node.left, value, path)
    else:
        node.right = self._insert(node.right, value, path)
    return node

Search — the same walk, returning true when the comparison lands on the value:

def search(self, value):
    """O(h): the same downward walk. At each node, done if equal, else go to the
    side that could contain the value. Every comparison eliminates a whole subtree."""
    node = self.root
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False

def __contains__(self, value):
    return self.search(value)

Delete is the one with real subtlety — three cases, the hardest being a node with two children, which is replaced by its in-order successor:

def delete(self, value):
    """O(h): three cases. A leaf just vanishes. A node with one child is replaced
    by that child. A node with two children is replaced by its in-order successor —
    the smallest value in its right subtree — which is then deleted from there. The
    successor is chosen because it preserves the BST ordering."""
    if value in self:
        self.root = self._delete(self.root, value)
        self._n -= 1

def _delete(self, node, value):
    if node is None:
        return None
    if value < node.value:
        node.left = self._delete(node.left, value)
    elif value > node.value:
        node.right = self._delete(node.right, value)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        succ = node.right               # find the in-order successor
        while succ.left is not None:
            succ = succ.left
        node.value = succ.value
        node.right = self._delete(node.right, succ.value)
    return node

Watch it work

Here's a binary search tree built by inserting seven values in the order 5, 3, 8, 1, 4, 7, 9. Green is the node just inserted; blue is the search path it walked to get there; dark nodes are settled. Step through it and watch the structure emerge: 5 becomes the root, 3 goes left of it, 8 right, and each later value walks down the comparisons — following blue — until it reaches an empty spot and hangs there in green. By the end the tree has exactly the shape whose in-order traversal, from the last chapter, reads out 1, 3, 4, 5, 7, 8, 9 — sorted:

The complete code

Both versions in one place — flip between them. The from-scratch tab is our BST with insert, search, and the three-case delete. The library tab is the standard library's closest structures: a bisect-maintained sorted list (ordered but O(n) insert) and a set (O(1) but unordered) — the two things a BST sits between. For a real balanced BST you'd reach for the third-party sortedcontainers.

"""The binary search tree — a binary tree with one rule that makes it a searchable,
ordered container: for every node, everything in its left subtree is smaller and
everything in its right subtree is larger.

That rule turns search, insert, and delete into a single idea: walk down from the
root, going left or right by comparing, until you find the value or the spot for it.
Each step drops a level, so the work is the tree's height — O(log n) when the tree is
balanced, O(n) when it isn't. In-order traversal reads the whole thing out sorted. The
catch, which the next two chapters fix, is that nothing here keeps the tree balanced.
"""


class Node:
    __slots__ = ("value", "left", "right")

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


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

    # region: insert
    def insert(self, value, probe=None):
        """O(h): walk down comparing — left if smaller, right if larger — until you
        fall off the tree, then hang the new node there. Duplicates are ignored (a
        BST models a set). h is the height: log n balanced, n degenerate."""
        if self.search(value):
            if probe is not None:
                probe.append({"path": [], "new": value})
            return
        path = []
        self.root = self._insert(self.root, value, path)
        self._n += 1
        if probe is not None:
            probe.append({"path": path, "new": value})

    def _insert(self, node, value, path):
        if node is None:
            return Node(value)
        path.append(node.value)
        if value < node.value:
            node.left = self._insert(node.left, value, path)
        else:
            node.right = self._insert(node.right, value, path)
        return node
    # endregion

    # region: search
    def search(self, value):
        """O(h): the same downward walk. At each node, done if equal, else go to the
        side that could contain the value. Every comparison eliminates a whole subtree."""
        node = self.root
        while node is not None:
            if value == node.value:
                return True
            node = node.left if value < node.value else node.right
        return False

    def __contains__(self, value):
        return self.search(value)
    # endregion

    # region: delete
    def delete(self, value):
        """O(h): three cases. A leaf just vanishes. A node with one child is replaced
        by that child. A node with two children is replaced by its in-order successor —
        the smallest value in its right subtree — which is then deleted from there. The
        successor is chosen because it preserves the BST ordering."""
        if value in self:
            self.root = self._delete(self.root, value)
            self._n -= 1

    def _delete(self, node, value):
        if node is None:
            return None
        if value < node.value:
            node.left = self._delete(node.left, value)
        elif value > node.value:
            node.right = self._delete(node.right, value)
        else:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            succ = node.right               # find the in-order successor
            while succ.left is not None:
                succ = succ.left
            node.value = succ.value
            node.right = self._delete(node.right, succ.value)
        return node
    # endregion

    def __len__(self):
        return self._n

    def inorder(self):
        out = []

        def rec(node):
            if node is not None:
                rec(node.left)
                out.append(node.value)
                rec(node.right)

        rec(self.root)
        return out

"""Python has no built-in balanced BST — the third-party `sortedcontainers.SortedList`
is what you'd actually use for ordered O(log n) operations. In the standard library the
two nearest things sit on either side of the BST's trade-off:

  - A sorted list kept with `bisect.insort` is ordered, but each insert is O(n) because
    the array shifts — the array's weakness a BST is meant to fix.
  - A `set`/`dict` gives O(1) membership but NO order — you can't get its minimum or its
    keys in sorted order in less than O(n).

The BST's pitch is "both": ordered operations AND O(log n) inserts. The face-off shows
it beating the sorted list on insert-heavy work while keeping the order the set throws
away.
"""
import bisect


# region: sorted_list
def build_sorted_list(values):
    """Keep a sorted list via bisect: O(log n) to find the spot, but O(n) to insert
    because every later element shifts. Ordered, but insert-heavy workloads suffer."""
    a = []
    for v in values:
        i = bisect.bisect_left(a, v)
        if i >= len(a) or a[i] != v:
            a.insert(i, v)                  # the O(n) shift
    return a
# endregion


# region: dict_set
def build_set(values):
    """A set: O(1) membership, but unordered. No min, no max, no sorted iteration in
    less than O(n) — the ordering a BST keeps and a hash table discards."""
    return set(values)
# endregion

Scratch vs library

The face-off tells a crossover story. At small sizes the sorted list wins, because its insert — a bisect plus a C list.insert — has a tiny constant even though it's O(n). But O(n) per insert is O(n²) to build, and by 200000 elements our BST, at O(n log n) total, overtook it decisively: about 432 ms for the BST against 1140 ms for the sorted list, 2.6 times faster, and the gap widens with size. That's the BST's asymptotic advantage finally beating the array's constant — the exact crossover the complexity chapter promised. Meanwhile the set built in 9 ms, an order of magnitude faster than either — but it's unordered, so it can't do a single one of the ordered queries the BST exists for. The comparison to remember isn't the speed; it's the capability. You pay the BST's log factor to get order the hash table can't give you at any speed.

Where you'll actually meet it

You meet balanced binary search trees whenever data needs to stay ordered under updates. std::map and std::set in C++, TreeMap and TreeSet in Java, and ordered maps in many languages are balanced BSTs (usually red-black trees). Database indexes are their disk-based cousins, B-trees, a later chapter. Any "keep a leaderboard sorted as scores change," "find the next event after now," or "count how many values fall in this range" problem is a BST underneath. The plain version here is rarely used directly — its balanced descendants are — but every one of them is this structure plus a rule to keep it short.

Takeaways

A binary search tree orders its values with the invariant "smaller left, larger right," which makes search, insert, and delete a single downward walk of length equal to the tree's height, and makes in-order traversal yield sorted output. Balanced, that height is $O(\log n)$ and you have a fast ordered container — sorted iteration, ranges, min, max, successor — that a hash table can't match. Its fatal flaw is that it doesn't balance itself, so sorted input degrades it to an $O(n)$ linked list.

That flaw is the whole subject of the next chapter. The AVL tree is a BST that watches its own balance after every insert and delete and performs rotations — local restructurings that shuffle a few pointers — to guarantee the height stays $O(\log n)$ no matter what order the data arrives in. It's the BST made safe to actually use.