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.
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 is faster for lookup alone
but can't give you sorted order or "find the next value greater than X" cheaply.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.