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.
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.
x to the current
node: go left if smaller, right if bigger, until you fall off the tree (hit a missing child),
then attach a new node there. O(h), where h is the tree's height.x (found) or you fall off the tree (not found). O(h).O(h).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.
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.
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.
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.
O(log n) — a plain hash map's O(1) average
lookup is the usual trade, but it's not that simple once you measure it: against this site's own
hash table, the hash map wins when both store the
same native string keys (roughly 1.7x-3x faster), but loses to this page's own
numeric-keyed tree once it has to convert each key through String() first (roughly
1.4x-2.9x slower) — see Measuring against Hash
Table below. Either way, a hash map still can't give you sorted order or "find the next
value greater than X" cheaply.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.
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.
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.