Cairn
data structures · first tree · O(log n) average, O(n) worst case

↩ back to Node-Linked Trees

Binary Search Tree

A binary search tree keeps binary search's halving trick, but frees it from living in an array. Every node holds a value and up to two children — left and right — under one rule: everything in a node's left subtree is smaller, everything in its right subtree is bigger. Following that rule down from the root is exactly binary search's "check the middle, discard a half" move, except now there's no array to shift when you insert or delete. A sorted array gives you O(log n) search but O(n) insertion; a binary search tree gives you O(log n) search, insertion, and deletion — all three, as long as the tree stays roughly balanced.

Try it

Insert or search a number and watch the comparison path light up as it walks down from the root. Delete a number and the tree redraws with whichever of the three deletion cases applied described below the tree. Values must be numbers — order is the entire point of the structure, so there's no "which came first" tie-break the way a plain list has.

Loaded a sample tree. Insert, search, or delete a number — try one that isn't there.

Core operations

Every one of these costs is really "the height of the tree," not "the number of nodes." That distinction is the whole story of this data structure — see Pitfalls.

The two-children delete case

You can't just remove a node that has two subtrees hanging off it — both need a new parent, and neither subtree's root can take the other's place without breaking the ordering rule. The standard fix: find the node's in-order successor — the smallest value in its right subtree, found by walking left from that right child until there's nowhere further left to go. That successor is guaranteed to have no left child (if it did, that child would be even smaller and further left). Copy the successor's value into the node being deleted, then delete the successor itself from the right subtree — which is now a plain leaf-or-one-child delete, a case already handled. The in-order predecessor (largest value in the left subtree) works exactly as well by symmetry; the reference implementation below picks the successor.

Reference implementation

class BinarySearchTree {
  #root = null;

  insert(x) {
    const node = { value: x, left: null, right: null };
    if (this.#root === null) { this.#root = node; return; }
    let curr = this.#root;
    while (true) {
      if (x === curr.value) return; // duplicates ignored
      if (x < curr.value) {
        if (curr.left === null) { curr.left = node; return; }
        curr = curr.left;
      } else {
        if (curr.right === null) { curr.right = node; return; }
        curr = curr.right;
      }
    }
  }

  contains(x) {
    let curr = this.#root;
    while (curr !== null) {
      if (x === curr.value) return true;
      curr = x < curr.value ? curr.left : curr.right;
    }
    return false;
  }

  delete(x) {
    this.#root = this.#deleteNode(this.#root, x);
  }

  #deleteNode(node, x) {
    if (node === null) return null; // not found, nothing to do
    if (x < node.value) { node.left = this.#deleteNode(node.left, x); return node; }
    if (x > node.value) { node.right = this.#deleteNode(node.right, x); return node; }
    // x === node.value: this is the node to remove
    if (node.left === null) return node.right;   // leaf or one-child(right)
    if (node.right === null) return node.left;   // one-child(left)
    let succ = node.right;                        // two children: find in-order successor
    while (succ.left !== null) succ = succ.left;
    node.right = this.#deleteNode(node.right, succ.value);
    node.value = succ.value;
    return node;
  }

  inorder() {
    const out = [];
    const walk = (node) => {
      if (node === null) return;
      walk(node.left);
      out.push(node.value);
      walk(node.right);
    };
    walk(this.#root);
    return out;
  }
}

Notice inorder() — walking left subtree, then the node, then right subtree — always visits every value in sorted order, for any valid binary search tree. That's a useful sanity check on its own: if inorder() ever produces a value out of order, the tree's invariant has been violated somewhere. The interactive demo above uses an equivalent iterative insert/search and a recursive delete with the same three-case logic, plus extra bookkeeping to record the comparison path and which delete case fired, purely to drive the highlighting and log text — the algorithm itself is identical. Verified with 30,000 randomized insert/delete/contains operations against a plain JavaScript Set as a reference model (checking contains agreement and periodic inorder() sortedness), plus explicit edge cases: empty tree, single node, duplicate inserts, deleting a value that isn't present, and one deterministic tree exercising all three delete cases by hand. The demo's own path-tracking variant got a separate 20,000-trial pass against the same Set model, checking that its reported found/existed flags match and that the tree stays a valid BST (every node strictly between its ancestors' bounds) after every operation. See /tmp/bst_test.js, scratch, not committed.

Pitfalls

Insertion order determines shape. Insert already-sorted data — 1, 2, 3, 4, 5, in that order — and every new node becomes the previous one's right child. There's no branching at all: the "tree" is a straight line, and every operation degrades to O(n), exactly as bad as a linked list. The O(log n) claim above only holds when the tree is reasonably balanced — height proportional to log(number of nodes) — and plain insertion as described here makes no attempt to guarantee that. This is exactly the gap that self-balancing variants like AVL trees and red-black trees close, by rotating nodes during insert/delete to keep height bounded; this entry doesn't implement those rotations. Measured live: sorted insertion produces a tree whose height is exactly n, against random insertion's ~log n — see Graceful Degradation vs. Cliffs for the real numbers and how this compares to other structures' own worst cases.

The two-children case, done wrong. The tempting shortcut is to just move the whole successor node up rather than copying its value and deleting it from the right subtree — but the successor may itself have a right child, and naively promoting it loses that child's whole subtree. Copy the value, then recursively delete the successor (a strictly simpler case, since a leftmost node has no left child) — never skip the second half.

Duplicate values are ambiguous, not handled. The reference implementation above silently ignores an insert of a value already present. That's one reasonable choice — others are storing a count per node, or breaking ties by allowing duplicates on (say) the right side consistently. Pick one and apply it everywhere; mixing conventions mid-tree breaks the invariant that inorder() is sorted.

Where binary search trees show up

Measuring against Hash Table

The section above says a plain hash map is faster for lookup — true by Big-O (O(1) average vs. this page's own O(log n)), but not always true in wall-clock terms once the key type is pinned down. This instruments the exact contains shown in the reference implementation above and hash table's own shipped has/#hash directly — no reimplementation — correctness-checked against each other first with explicit present/absent probes (0 mismatches over 80,000 numeric-key probes and 40,000 string-key probes), then timed on random keys from 1,000 to 1,000,000 entries, build order alternated trial to trial to cancel out cache-warming bias.

With native string keys — the same 'key' + i convention the hash table's own instrumented demo already uses, so neither side pays an unusual cost — the hash map wins as the claim above expects: roughly 1.7x-3x faster across the full size range, even though the tree needs only about 10-20 node visits per lookup (growing slowly with log n) against the hash map's own near-constant ~1 bucket entry touched. Comparison count favors the hash map here too, not just the Big-O.

Swap in numeric keys instead — the same x values this page's own insert/contains already store — and the hash map has to fold every key through its own String(key) conversion before it can hash it at all, a cost the tree's raw numeric </=== comparisons never pay. That conversion, plus the per-entry bucket.some(entry => entry[0] === key) closure call even for a bucket holding just one entry, costs more than enough nanoseconds to flip the result: the tree wins by roughly 1.4x-2.9x across the same size range, despite doing strictly more comparisons by count. Same two structures, same claim, opposite verdict — the deciding factor isn't the algorithm, it's what kind of key you hand it.

100,000 keys, the same insert/contains and put/has shown above and on the hash table page — pick a key type and run it yourself, timed in this browser, right now.

This runs 100,000 keys rather than the full 1,000-to-1,000,000 sweep behind the numbers above — enough that the win stops being noise, still fast enough to click and watch. Five timed trials, build order alternated so neither structure always goes first, one untimed warm-up pass before any of them count so the JIT isn't still compiling on trial one; the log reports every trial, not just the median, plus a same probe this page's own correctness check above uses (2,000 random present/absent keys checked against each other) so a "faster" result is never silently wrong. Below 100,000 keys this flips unpredictably — run it at, say, 10,000 and the native-string case still favors the hash table, but numeric keys don't reliably favor the tree the way they do here; there isn't enough work yet for the real cost difference to outrun run-to-run JIT/GC noise. Expect this run to land in the same direction as the claim above — the exact multiple will differ from the frozen numbers, because this is actually running on your machine, in your browser, right now, not reporting a number from whatever machine happened to build this page.

Complexity

Time: insert, contains/search, and delete are all O(h) where h is the tree's height — O(log n) on average for a tree built from randomly-ordered data, but O(n) in the worst case (a tree degenerated into a line, per the Pitfalls section above). inorder() is always O(n), since it must visit every node. Space: O(n) for n nodes, plus two pointers per node (left and right) — one more than a linked list spends per node, in exchange for that O(log n) search when balanced.

This is the baseline every self-balancing variant below exists to fix. See Choosing a Search Tree for when a plain BST is still the right call versus AVL, red-black, splay, or B-tree.