Binary search tree

Cost and properties

search / insert	~1.39 lg n if keys arrive randomly
worst case	n — sorted input builds a list
ordered ops	min, max, floor, rank, range
space	3 pointers per node

Reference: Sedgewick & Wayne, §3.2.

Binary search tree in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class BST:
    # SYMMETRIC ORDER: every key in x.left  <  x.key
    #                  every key in x.right >  x.key

    class _Node:
        __slots__ = ('key', 'val', 'left', 'right', 'n')
        def __init__(self, key, val):
            self.key, self.val = key, val
            self.left = self.right = None
            self.n = 1                    # size of this subtree

    def __init__(self):
        self.root = None

    def get(self, key):
        x = self.root
        while x is not None:              # one compare per level
            if key < x.key:
                x = x.left
            elif key > x.key:
                x = x.right
            else:
                return x.val
        return None                       # fell off the tree: not present

    def put(self, key, val):
        self.root = self._put(self.root, key, val)

    def _put(self, x, key, val):
        if x is None:
            return BST._Node(key, val)    # new node hangs where the search ended
        if key < x.key:
            x.left = self._put(x.left, key, val)
        elif key > x.key:
            x.right = self._put(x.right, key, val)
        else:
            x.val = val                   # key already there: overwrite
        x.n = 1 + self._size(x.left) + self._size(x.right)
        return x

    def _size(self, x):
        return 0 if x is None else x.n

Why it works

Symmetric order, and what it buys

The invariant is every key in the left subtree is smaller, every key in the right subtree is larger. It is what makes the search work — one comparison eliminates an entire subtree — and it also gives you the ordered operations a hash table cannot: minimum, maximum, floor, ceiling, rank, select, and an in-order traversal that returns the keys sorted.

Shape follows insertion order

A BST is not self-balancing: its height is decided by the order keys arrive. Random keys give ~1.39 lg n compares (only 39% above the optimum). Sorted keys give a path of length n and every operation becomes linear — and sorted input is exactly what real data tends to be. Run the sorted insert preset.

This is the motivation for the next lecture: red-black BSTs guarantee the height instead of hoping for it.

Recursive put, read carefully

_put returns the subtree root, and the caller reassigns x.left = self._put(x.left, …). That reassignment is almost always a no-op for a plain BST — but it is what lets a balanced tree replace the subtree root after a rotation, without any parent pointers. Learning the pattern here makes the red-black code readable later.

Deletion is the ugly part

Hibbard deletion replaces a doubly-linked node with its successor. It works, but it is asymmetric — always taking the successor — and after many random insert/delete pairs the tree's height degrades to √n. Nobody had a simple, provably balanced deletion for decades, which is a fair sign of how hard the problem is; red-black trees solve it properly.

What to try in the animation

Insertion order decides the shape. Compare the default with sorted insert: the same keys, one balanced-ish tree and one linked list.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• course example — insert: S E A R C H X M P L · search: P
• sorted insert (worst case) — insert: A C E H L M P R S X · search: X
• search for a missing key — insert: S E A R C H X M P L · search: B
• numbers — insert: 50 30 70 20 40 60 80 35 45 · search: 45

Open Binary search tree in the player →