Binary Search Trees

The 10-second versionCopy Anchor Link

A binary search tree is an ordinary binary tree with one rule bolted on: everything in a node's left subtree is smaller than the node, and everything in its right subtree is bigger. That single rule turns a hierarchy into a live index. Search, insert, delete, minimum, maximum, predecessor, and successor all walk one root-to-leaf path, so they cost O(log n) — as long as the tree stays bushy. The catch is in that last clause: feed it already-sorted data and the tree degenerates into a linked list, and every operation slides back to O(n). That catch is precisely what summons the next three pages.

Why this existedCopy Anchor Link

Picture the two structures you already have, and how each is half of what you want.

• A sorted array gives you binary search: O(log n) lookups, because you can halve the range by jumping to the middle. But inserting into the middle means shifting everything after it — O(n).
• A linked list gives you O(1) insertion — just relink a pointer. But finding the right spot means walking the whole thing — O(n) search.

You wanted a structure that is fast to search and cheap to change. For years, that looked like a contradiction: halving needs sorted order, and sorted order in an array is expensive to maintain.

The idea that dissolved the contradiction — put the sortedness in the pointers instead of the positions — appeared in the literature around 1960. Thomas N. Hibbard gave the first careful analysis in 1962, proving that with random insertions the average search path is about 1.39 · log₂ n deep. In 1973, Knuth's The Art of Computer Programming, Volume 3 turned the BST into the default "symbol table" — the structure every language used to map names to values. And, tellingly, the same book flagged the exact failure mode that the very next page exists to fix: the shape depends entirely on the order you insert.

Why it mattered then: an ordered tree is the first structure where search and update both stay logarithmic on the same object. No more choosing between a fast-read array and a fast-write list.

Inside the inventor's headCopy Anchor Link

Sit with binary search for a minute. It's fast because each comparison throws away half of what's left. But that halving only works because the data sits in a row, sorted, so "the middle" is a real, findable place.

The leap is to ask: what if "sorted" didn't need a row? Keep the same halving, but let each comparison send you down a pointer instead of to an index. Then re-sorting after an insert is just re-pointing a couple of links — O(1) — while the halving survives.

So the naive first instinct — "just keep a sorted array and be careful" — buys you a fast search but a slow insert:

// Search is O(log n): halve, halve, halve...function search(a, key) {  let lo = 0, hi = a.length - 1;  while (lo <= hi) {    const mid = (lo + hi) >> 1;    if (a[mid] === key) return mid;    if (a[mid] < key) lo = mid + 1; else hi = mid - 1;  }  return -1;}// ...but every insert shifts the tail: O(n).function insertSorted(a, key) {  let i = a.length;  while (i > 0 && a[i - 1] > key) { a[i] = a[i - 1]; i--; }  a[i] = key;}

The fix is to make the rule an invariant — and then the whole structure is correct by construction. Here's the rule, written as a check you can run on any tree. Notice it doesn't compare a node only to its parent; it carries the whole allowed range down the tree:

// A tree is a BST iff every node lies strictly inside the range its ancestors allow.const isBST = (n, lo = -Infinity, hi = Infinity) => {  if (!n) return true;  if (n.key <= lo || n.key >= hi) return false;  return isBST(n.left, lo, n.key) && isBST(n.right, n.key, hi);};

That range-carrying detail is the trap. Checking only "left child is smaller and right child is bigger" passes some trees that are not legal BSTs — a shallow check misses a deep violation. The invariant is about subtree ranges, not parent-child pairs.

Here is the before-and-after that started the whole panic — the same rules, and two wildly different outcomes purely because of the order the keys arrived in:

The first tree came from a scrambled insert order and has height 3. The second came from inserting the keys already sorted, and it is a straight line — a linked list wearing a tree costume. Same code, same rule, and a completely different cost.

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

Search and insert are the same walk. You compare, and you go left or right; you stop when you find the key (search) or fall off into an empty slot (insert):

The invariants that make it correctCopy Anchor Link

1. The BST property. For every node, all keys in its left subtree are smaller and all keys in its right subtree are bigger — a range that every node must satisfy, not just a parent-child comparison.
2. No duplicates (by convention). Equal keys are usually rejected or updated, never inserted twice, so the "less / greater" tests stay exhaustive.
3. In-order traversal is sorted. This is the invariant made visible: run the inorder walk from the last page and the keys stream out in ascending order, for free.
4. Height rules everything. Every operation walks one root-to-leaf path, so all of them are O(h) — which is O(log n) only while the tree stays bushy.

A worked traceCopy Anchor Link

Insert 50, 30, 70, 20, 40, 60, 80 in that order:

• 50 becomes the root.
• 30 is less than 50 → left child. 70 is greater → right child.
• 20 is less than 50, less than 30 → 30's left. 40 is less than 50, greater than 30 → 30's right.
• 60 and 80 mirror into 70's children.

Height is 3, and every search costs at most 3 comparisons. Now insert 10, 20, 30, 40, 50 — already sorted:

• Each new key is bigger than every existing one, so each insert walks all the way right and becomes a right child.
• The result is a right-leaning chain of height 5. Search is now a linear scan.

Same operations, same code — and the shape decides whether you get O(log n) or O(n).

It in codeCopy Anchor Link

A full, working BST: insert, search, minimum, and the successor — the smallest key strictly greater than a given one, which is the operation ordered databases are built on.

class Node {  constructor(key) { this.key = key; this.left = null; this.right = null; }}function insert(root, key) {  if (!root) return new Node(key);             // open slot found on the way down  if (key < root.key)      root.left  = insert(root.left, key);  else if (key > root.key) root.right = insert(root.right, key);  return root;                                 // equal → ignore}function search(root, key) {  while (root && root.key !== key)    root = key < root.key ? root.left : root.right;  return root;                                 // null if absent}const minNode = (n) => { while (n && n.left) n = n.left; return n; };function successor(root, key) {                 // smallest key strictly greater than `key`  let succ = null;  while (root) {    if (key < root.key) { succ = root; root = root.left; }    else                { root = root.right; }  }  return succ;}

Cost tableCopy Anchor Link

The magic word is balanced. A random insertion order tends to produce a reasonably bushy tree; a sorted insertion order produces a disaster. The data structure never promised O(log n) — it promised O(h), and left the height to you.

Where you meet it todayCopy Anchor Link

• Ordered maps and sets. std::map, Java's TreeMap, C#'s SortedDictionary all expose the BST contract: keys in sorted order, with floor/ceiling/range queries. (Internally most use a red-black tree — keep reading.)
• Database indexes. A B-tree is the BST idea reorganized for disk blocks, and its "predecessor/successor" operations are exactly how ORDER BY and range scans work.
• Symbol tables and autocomplete. "Find the largest key below this one" is what powers floor() lookups and the nearest-match behavior of a compiler's name resolution.
• File systems. Directory entries and extent maps are ordered trees so the OS can ask "which file covers byte offset x?" quickly.

// Prune the walk: only descend where a match is still possible.function range(n, lo, hi, out = []) {  if (!n) return out;  if (lo < n.key)                       range(n.left, lo, hi, out);   // skip if n.key <= lo  if (lo <= n.key && n.key <= hi)       out.push(n.key);  if (n.key < hi)                       range(n.right, lo, hi, out);  // skip if n.key >= hi  return out;}

RecapCopy Anchor Link

• A BST adds one rule to a binary tree: left subtree smaller, right subtree bigger, for the whole subtree — not just the immediate child.
• That rule makes search, insert, delete, min, max, and successor all cost O(h), where h is the height.
• In-order traversal reads out sorted — the invariant you can see.
• When h ≈ log n you win; when the tree degenerates into a chain, h = n and you're back to a linked list.
• Insertion order controls the height. That's the vulnerability the next page fixes.

Next up: AVL Trees — the first self-balancing tree, which keeps the height logarithmic no matter what order you insert.