Binary Search Trees
Imagine building a dictionary that must support fast lookups, insertions, and deletions of keys. It must also list all keys in sorted order at any moment. An array can be sorted for fast binary search. But insertion and deletion cost O(n) due to shifting elements. A Hash Table gives O(1) average lookup but destroys order. There is no way to efficiently ask for the next-largest key. The binary search tree (BST) solves this tension. It keeps keys in a structure that is simultaneously ordered and dynamic. It supports search, insertion, deletion, minimum, maximum, and successor queries. All these run in time proportional to the tree's height. This idea underlies enormous swaths of real infrastructure. Database indexes, in-memory ordered maps (like C++'s `std::map`, Java's `TreeMap`), and the scheduling structures inside operating systems all descend from the binary search tree. The BST is also the conceptual seed for a whole family of self-balancing structures. These include AVL Trees, red-black trees, and treaps. They guarantee logarithmic height no matter what sequence of operations arrives. Understanding the plain BST first, warts and all, is essential. Only then can we appreciate why those more elaborate structures exist. The central insight is a single ordering invariant applied recursively. For every node, everything in its left subtree is smaller. Everything in its right subtree is larger. This one rule is maintained under insertion and deletion. It is enough to make an entire tree behave like a sorted, searchable, dynamically resizable array. But the same rule has a sharp weakness. If keys arrive in sorted order, the tree degenerates into a linked list. Every operation then collapses from the hoped-for O(log n) to O(n). This article builds the BST from its defining invariant. It walks through search, insertion, and deletion. This includes the subtle two-child case and the successor operation it depends on. It then confronts honestly the gap between two things. These are the "expected" logarithmic behavior and the worst-case linear behavior. This gap motivates why balanced trees were invented at all.
- A BST maintains the BST property: left subtree keys < node key < right subtree keys, recursively, for every node.
- Search, insert, and delete all follow a single root-to-leaf path, so each costs O(h) where h is the tree's height.
- Insertion always creates a new leaf; it never needs to touch existing structure elsewhere in the tree.
- Deleting a node with two children requires finding its in-order successor (or predecessor) to replace it.
- Height h ranges from Θ(log n) for a balanced tree to Θ(n) for a degenerate (sorted-insertion) tree — same code, wildly different speed.
- BSTs are the direct ancestor of self-balancing trees like AVL Trees and red-black trees, which force h = O(log n) always.
A binary search tree turns a single local ordering rule — left smaller, right larger, at every node — into global sorted-order search, insertion, and deletion, all in time proportional to the tree's height.
The idea
A binary search tree is a binary tree in which every node stores a key (and, typically, associated data), and the tree satisfies the BST property: for any node `x`, every key in the left subtree of `x` is strictly less than `x.key`, and every key in the right subtree of `x` is strictly greater than `x.key`. This property must hold not just between a node and its immediate children, but between a node and every node in either subtree — it is a global, recursive constraint, not just a local comparison. This single invariant has a beautiful consequence: an in-order traversal (left, node, right) of a BST visits keys in strictly increasing order. This connects the BST directly to Tree Traversals — the sortedness of the structure is not an accident but a direct restatement of the ordering rule under recursive descent. It also means a BST is really a shape-flexible sorted sequence: the same set of keys can be arranged into many different valid BST shapes (some tall and skinny, some short and bushy), and all of them, when traversed in-order, print the identical sorted list. The operations search, minimum, maximum, successor, predecessor, insert, and delete all exploit the BST property to prune the search space by roughly half at each step (in the balanced case) — never needing to look at the whole tree. Every one of these operations follows a path from the root either downward to a target location or, for successor/predecessor, briefly upward. Consequently, the running time of every core BST operation is proportional to the height `h` of the tree, not to the number of nodes `n`. This is the crucial fact the rest of the article is built around, and it is also the crucial fact that makes BSTs both powerful and fragile.
How it works
Search. To find a key `k`, start at the root. If the current node is `nil`, the key is absent. If `k` equals the current key, return it. If `k` is smaller, recurse left; if larger, recurse right. Each comparison eliminates an entire subtree from consideration.
Minimum / Maximum. The minimum key is found by walking left children until hitting a node with no left child; symmetrically for maximum and right children.
Successor. The in-order successor of node `x` (the next key in sorted order) has two cases: 1. If `x` has a right subtree, the successor is the minimum of that right subtree. 2. If `x` has no right subtree, the successor is the lowest ancestor of `x` whose left child is also an ancestor of `x` (i.e., walk up until you move from a right child to its parent).
Insertion. Walk down from the root exactly as in search, but track the parent pointer. When you fall off the tree (reach `nil`), attach a new leaf there, on the correct side determined by the last comparison. Insertion never rearranges existing nodes — the new key always becomes a leaf.
Deletion. This is the operation with real subtlety, split into three cases for deleting node `z`:
- No children: simply remove `z`, updating its parent to point to `nil`.
- One child: splice `z` out, linking `z`'s parent directly to `z`'s single child.
- Two children: find `z`'s in-order successor `y` (the minimum of `z`'s right subtree — guaranteed to have no left child by minimality). Copy `y`'s key into `z`, then remove `y` from its original position using the no-child or one-child case (`y` has at most a right child, never a left one, since it is a leftmost node).
```pseudocode // A node has: key, left, right, parent (parent optional but convenient) function SEARCH(root, k): x = root while x != NIL and k != x.key: if k < x.key: x = x.left else: x = x.right return x // NIL if not found function MINIMUM(x): while x.left != NIL: x = x.left return x function MAXIMUM(x): while x.right != NIL: x = x.right return x function SUCCESSOR(x): if x.right != NIL: return MINIMUM(x.right) y = x.parent while y != NIL and x == y.right: x = y y = y.parent return y // NIL if x was the maximum function INSERT(root, z): // z is a new node with z.key set y = NIL x = root while x != NIL: y = x if z.key < x.key: x = x.left else: x = x.right z.parent = y if y == NIL: root = z // tree was empty elif z.key < y.key: y.left = z else: y.right = z return root function TRANSPLANT(root, u, v): // replaces subtree rooted at u with subtree rooted at v if u.parent == NIL: root = v elif u == u.parent.left: u.parent.left = v else: u.parent.right = v if v != NIL: v.parent = u.parent return root function DELETE(root, z): if z.left == NIL: root = TRANSPLANT(root, z, z.right) elif z.right == NIL: root = TRANSPLANT(root, z, z.left) else: y = MINIMUM(z.right) // in-order successor if y.parent != z: root = TRANSPLANT(root, y, y.right) y.right = z.right y.right.parent = y root = TRANSPLANT(root, z, y) y.left = z.left y.left.parent = y return root ``` The `TRANSPLANT` helper is the key simplification: it abstracts "replace this subtree with that subtree" so the three deletion cases can share logic. Note the guard `if y.parent != z` — when the successor `y` is immediately `z`'s right child (i.e., `z.right` has no left subtree), transplanting `y.right` into `y`'s old spot before re-linking `y` under `z` would incorrectly overwrite pointers; the guard avoids that redundant step.
Complexity & correctness
Time complexity. SEARCH, INSERT, MINIMUM, MAXIMUM, and (amortized over a traversal) SUCCESSOR all run in O(h) time, where `h` is the height of the tree, because each follows a single path from the root and does O(1) work per node visited. DELETE also runs in O(h): locating `z` is O(h), and locating its successor `y` (a MINIMUM call within `z`'s right subtree) is at most another O(h), with O(1) pointer surgery afterward. The catch is what `h` can be:
- Best/average case (roughly balanced tree): `h = O(log n)`. If each subtree holds roughly half the remaining nodes, the height satisfies `T(n) = T(n/2) + O(1)`, giving `h = O(log n)`, and all operations are logarithmic. Random insertion orders produce expected height `O(log n)` as well — a classical result showing that a random BST is, with high probability, well-balanced even without any explicit balancing logic.
- Worst case (degenerate tree): `h = Θ(n)`. Inserting keys already in sorted order (`1, 2, 3, …, n`) makes every new key larger than all existing keys, so each insertion attaches to the rightmost path — producing a structure that is really a linked list wearing a tree's clothing. Search, insert, and delete all degrade to O(n).
This gap is not a minor footnote — it is the single most important fact about plain BSTs, and it is exactly the motivation for augmenting the structure with balance guarantees, as AVL Trees and red-black trees do.
Space complexity. A BST on `n` keys uses O(n) space: one node per key, each storing a constant number of pointers (`left`, `right`, optionally `parent`) plus the key/data payload. No auxiliary structures are needed beyond the tree itself.
Correctness argument. The correctness of every operation rests entirely on maintaining the BST invariant as an inductive loop invariant during descent: Search invariant: at the start of each loop iteration, if the target key `k` exists in the tree, it exists in the subtree rooted at the current node `x`. Initially this holds trivially (x = root). If `k < x.key`, the BST property guarantees `k` cannot be in `x`'s right subtree or in `x` itself, so it must be in the left subtree if present anywhere — preserving the invariant after moving left. The symmetric argument holds for moving right. When `x` becomes `NIL`, the invariant says `k` would have had to be in an empty subtree, so `k` is absent. This proves search correctness by induction on loop iterations. Insertion correctness: insertion runs the identical descent, so by the search invariant it terminates at the unique `NIL` position where `k` belongs relative to every ancestor's key. Attaching the new node there preserves the BST property for every ancestor (the new key is consistently on the correct side of each one) and trivially satisfies it locally (a leaf has no subtrees to violate). Deletion correctness (two-child case): the in-order successor `y` of `z` is, by definition, the smallest key strictly greater than `z.key` in the whole tree. Because `y = MINIMUM(z.right)`, `y` has no left child (a minimum node can't have a left child, or something smaller would exist). Overwriting `z`'s key with `y`'s key preserves the BST property, because every key in `z`'s original left subtree is still less than `y.key` (they were less than `z.key ≤ y.key`), and every remaining key in `z`'s right subtree is still greater than `y.key` (since `y` was the minimum there, and removing it doesn't change that all other right-subtree keys exceed it). Removing `y` from its original spot is safe via the one-child/no-child case, since `y` has at most a right child.
Worked example
Start from an empty tree and insert keys in this order: 50, 30, 70, 20, 40, 60, 80, 35. This matches the figure above.
| Step | Insert | Path taken (comparisons) | Resulting attachment |
|---|---|---|---|
| 1 | 50 | tree empty | becomes root |
| 2 | 30 | 30 < 50 → left of 50 is NIL | 30 becomes left child of 50 |
| 3 | 70 | 70 > 50 → right of 50 is NIL | 70 becomes right child of 50 |
| 4 | 20 | 20 < 50, 20 < 30 → left of 30 is NIL | 20 becomes left child of 30 |
| 5 | 40 | 40 < 50, 40 > 30 → right of 30 is NIL | 40 becomes right child of 30 |
| 6 | 60 | 60 > 50, 60 < 70 → left of 70 is NIL | 60 becomes left child of 70 |
| 7 | 80 | 80 > 50, 80 > 70 → right of 70 is NIL | 80 becomes right child of 70 |
| 8 | 35 | 35 < 50, 35 > 30, 35 < 40 → left of 40 is NIL | 35 becomes left child of 40 |
Now run SEARCH(root, 35) (the dashed path in the figure): 1. At 50: `35 < 50`, go left. 2. At 30: `35 > 30`, go right. 3. At 40: `35 < 40`, go left. 4. At 35: match — return this node. Four comparisons, matching the height of the path (h ≈ 3–4 here), confirming O(h) behavior. Now DELETE(root, 30) — a two-child case, since 30 has left child 20 and right child 40: 1. `z = 30`, both children present, so find `y = MINIMUM(z.right) = MINIMUM(subtree rooted at 40)`. 2. Walk left from 40: 40 has left child 35, and 35 has no left child, so `y = 35`. 3. Since `y.parent (40) != z (30)`, first transplant `y` out of its old spot: replace 35 with `y.right` (NIL) as the left child of 40. 4. Set `y.right = z.right = 40` (and fix `40.parent = y`). 5. Transplant `z` (30) with `y` (35) at the top level: 50's left child becomes 35. 6. Set `y.left = z.left = 20` (and fix `20.parent = y`). Resulting subtree rooted where 30 used to be: 35 with left child 20 and right child 40 (which retains its own right child 60... wait, 40's children here: original tree had 40 as leaf with left child 35 only, so after removing 35, 40 has no children). Final in-order traversal of the whole tree: `20, 35, 40, 50, 60, 70, 80` — still perfectly sorted, confirming the invariant survived the deletion.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Forgetting `parent` pointer updates | Easy to update `left`/`right` of the new parent but skip `child.parent = newParent` | Always update both directions of every pointer swap, especially in `TRANSPLANT` |
| Two-child deletion without successor | Just deleting the node and reattaching one child arbitrarily breaks the BST property | Always replace with in-order successor (or predecessor) — never skip this step |
| Assuming average-case height always | Code is "correct" but silently becomes O(n) on sorted input | Use a self-balancing variant (AVL Trees, red-black trees) when adversarial input is possible |
| Confusing BST property with "children ordered" | Checking only `left.key < node.key < right.key` locally, missing deeper violations | The property must hold against every node in each subtree, not just direct children |
| Off-by-one in successor when node is the maximum | Walking up parent pointers without checking for `NIL` | SUCCESSOR must return `NIL` gracefully when no ancestor satisfies the turn condition |
| Duplicate keys mishandled | No consistent rule for where equal keys go breaks assumptions used elsewhere (e.g. successor uniqueness) | Decide and document a consistent tie-breaking rule (e.g., duplicates go right) |
Pioneers & history
The binary search tree emerged from a broader mid-20th-century push to organize data for efficient retrieval on early computers, blending ideas from information retrieval, symbolic computation, and combinatorics. Unlike some algorithms with a single clear inventor, BSTs crystallized gradually through work on tree-structured storage and searching, later formalized rigorously in the analysis-of-algorithms tradition.
Origins · 1 minDonald E. Knuth and how this was discovered
Knuth's multi-volume The Art of Computer Programming gave binary search trees their first fully rigorous treatment: precise algorithms, careful average-case and worst-case analyses, and connections to combinatorics (counting distinct BST shapes) and sorting theory. His analysis of random BST height — showing expected height O(log n) under random insertion — remains a foundational result taught in every algorithms course, and his notation and style shaped how tree-based data structures are described to this day.
Where this matters
Ordered in-memory maps and sets in standard libraries — C++'s `std::map`/`std::set`, Java's `TreeMap`/`TreeSet`, .NET's `SortedDictionary` — are implemented with balanced BST variants (typically red-black trees), directly extending the plain-BST algorithms described here. Database index structures, while usually B-trees on disk for I/O efficiency, share the exact same ordering invariant and successor/predecessor logic. Compilers and interpreters use BST-like structures for symbol tables when ordered iteration or range queries over identifiers are needed. Computational geometry algorithms (like sweep-line algorithms for segment intersection) maintain BSTs of active edges, relying on O(log n) insertion, deletion, and neighbor queries. Understanding plain BST mechanics — search descent, successor computation, and the two-child deletion case — is a prerequisite for every one of these production structures, and for the next step in this sequence: Augmenting Data Structures to support range queries, order statistics, and interval queries on top of the same balanced-tree skeleton.
Ask the tutor: How does adding a balance invariant (like AVL's height-difference rule) change the insertion and deletion algorithms compared to a plain BST?
What is the difference between a binary tree and a binary search tree?
A binary tree is any tree where each node has at most two children — no ordering constraint is implied. A binary search tree is a binary tree that additionally satisfies the BST property: for every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger. This extra invariant is what enables efficient searching, since comparisons at each node reliably eliminate half the remaining candidates (in the balanced case), whereas a generic binary tree offers no such guarantee and requires potentially visiting every node to find a key.
Why does deletion need the successor instead of just picking any child?
When deleting a node with two children, simply promoting one child (say, the left child) into the parent's position would orphan the other subtree with no valid place to attach it while preserving order. The in-order successor is the unique node whose key is just larger than the deleted key, and — crucially — it has no left child (since it's the minimum of the right subtree), so it can be removed from its original position using the simple one-child/no-child deletion case. Copying its key up (or, in pointer-based implementations, splicing it into place) keeps the entire tree's ordering invariant intact with minimal restructuring.
Can a BST have duplicate keys?
Standard BST definitions assume distinct keys, but real implementations often need to handle duplicates. A common convention is to route duplicates consistently to one side — for example, "equal keys go to the right subtree" — and to keep this rule consistent across insert, search, and delete. Some implementations instead store a count or a list of items per key node rather than creating a new node per duplicate. Without a consistent rule, successor/predecessor logic and even basic search correctness can break, since they implicitly assume a well-defined total order among distinct nodes.
Why is average-case BST height O(log n) for random insertions?
If keys are inserted in a uniformly random order, the height of the resulting BST is, with high probability and in expectation, O(log n) — a result formalized in Knuth's analysis of random tree shapes. Intuitively, a random insertion order is very unlikely to consistently pick keys that all land on one side, the way sorted input does; most root choices roughly split the remaining keys, similarly to how randomized Quicksort achieves expected O(n log n) time despite a worst-case O(n²). This is why a "typical" BST performs well in practice even without explicit rebalancing — but "typical" is not a guarantee, which is exactly why self-balancing trees exist for adversarial or structured inputs.
How does a BST relate to AVL trees and red-black trees?
AVL Trees and red-black trees are binary search trees with an added balance invariant enforced after every insertion and deletion. AVL trees require the heights of any node's two subtrees to differ by at most 1, while red-black trees use a coloring scheme with rules ensuring no root-to-leaf path is more than twice as long as any other. Both guarantee height O(log n) in the worst case, at the cost of extra bookkeeping (rotations, recoloring) on every update. All of their core search/insert/delete logic still descends directly from the plain BST algorithms described here — the balancing machinery is layered on top, not a replacement for it.
What is the space complexity of a BST, and are there hidden costs?
A BST storing n keys uses O(n) space: one node per key plus a constant number of pointers per node (left, right, and optionally parent). There is no asymptotic overhead beyond this, but constant factors matter in practice — storing a parent pointer roughly increases per-node memory by 33% (three pointers instead of two) in exchange for making SUCCESSOR and iterative traversal without recursion much simpler to implement. Some implementations omit the parent pointer entirely and instead maintain an explicit stack during traversal to save memory at the cost of slightly more complex code.
Is a BST ever a good choice over a hash table?
Yes, whenever you need operations a hash table cannot support efficiently: sorted iteration, range queries (all keys between a and b), finding the minimum/maximum, or successor/predecessor queries. A hash table gives O(1) average lookup but no ordering information whatsoever. A balanced BST gives O(log n) for search/insert/delete but also supports all order-based queries in O(log n) or O(log n + k) for a range of size k. The choice is a genuine tradeoff between raw lookup speed and the richer query capability that ordering provides.