Binary Search Trees

A binary search tree keeps keys ordered so search, insertion, and deletion cost O(h) where h is the height, ideally O(log n).

The ordering invariant

A binary search tree (BST) is a binary tree obeying one rule at every node: all keys in the left subtree are smaller, all keys in the right subtree are larger. This invariant lets you find a key by comparing and descending left or right, discarding half the remaining tree at each step, much like binary search on a sorted array.

Operations and cost

Search, insert, and delete all follow a root-to-leaf path, so each costs O(h) where h is the tree height. Insertion adds a leaf at the point where the search falls off. Deletion has three cases: a leaf is removed directly, a node with one child is spliced out, and a node with two children is replaced by its in-order successor.

• Search: O(h)
• Insert: O(h)
• Delete: O(h)
• In-order traversal yields keys in sorted order: O(n)

Height is everything

When keys arrive in random order the tree stays roughly balanced and h is about log n. But inserting already-sorted keys builds a degenerate tree that is really a linked list, with h equal to n and every operation O(n). This failure mode is exactly why self-balancing trees exist.

def search(node, key):
    while node:
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right
    return None

In-order traversal

Visiting left subtree, then node, then right subtree produces the keys in ascending order. This is what makes a BST useful beyond a hash table: it supports ordered queries, range scans, and finding the next-largest key, none of which a hash table can do efficiently.