Binary Search Trees

A binary search tree (BST) is a binary tree with an ordering invariant: every node's left subtree contains only smaller keys, and every node's right subtree contains only larger keys. The invariant means search, insert, and delete all reduce to a path from root to leaf — $O(h)$, where $h$ is the tree's height.

Search

Starting from the root, compare the target with the current key. If equal, found. If smaller, recurse left; if larger, recurse right. At most one path is traversed — $O(h)$.

Insert

Search until you find an empty slot, then put the new node there. The new node becomes a leaf, and the BST invariant holds automatically.

Delete

Three cases: 1. Leaf: just remove it. 2. One child: replace the node with its child. 3. Two children: replace the node with its in-order successor (smallest node in the right subtree), then delete the successor from the right subtree.

The balance problem

If you insert sorted data into a plain BST, you get a chain of right children — height $n - 1$. Every operation becomes $O(n)$. Self-balancing BSTs (AVL, red-black) enforce $O(\log n)$ height by performing rotations after each insert/delete. Java's TreeMap and C++'s std::map use red-black trees.

In-order = sorted

Walking a BST in-order yields all keys in ascending order. This is the most useful property of BSTs and the source of many problems: "find the k-th smallest element," "find the first key greater than x," "iterate keys in a range."

When to use one

Hash maps beat BSTs for plain key-value lookup ($O(1)$ vs $O(\log n)$). Use a BST when you need ordered iteration, range queries, predecessor/successor, or any operation that exploits the sort order.