Part 1 · Concepts · Trees
Binary search tree
A tree where every left subtree is smaller and every right subtree is larger, so search halves the space at each step.
How it works
Search, insert and delete walk down one path, so they cost O(h). Balanced, h is log n. If you insert sorted data, it becomes a linked list and h is n. Self-balancing trees (red-black, AVL) fix this with rotations. Deleting a node with two children: copy in the next larger value (the in-order successor), then delete that one.
| search / insert / delete | O(log n) balanced, O(n) skewed |
| min / max | O(h) |
| in-order walk | O(n), sorted |
Reach for it when
- Sorted data that changes often
- Range queries (everything between a and b)
- Floor and ceiling lookups
Implementation (JavaScript, tested)
class BST {
root = null;
insert(v) {
if (!this.root) {
this.root = node(v);
return;
}
let n = this.root;
while (true) {
if (v === n.val) return; // no duplicates
const side = v < n.val ? "left" : "right";
if (!n[side]) {
n[side] = node(v);
return;
}
n = n[side];
}
}
has(v) {
let n = this.root;
while (n) {
if (v === n.val) return true;
n = v < n.val ? n.left : n.right;
}
return false;
}
delete(v) {
this.root = del(this.root, v);
}
}
function del(n, v) {
if (!n) return null;
if (v < n.val) n.left = del(n.left, v);
else if (v > n.val) n.right = del(n.right, v);
else {
if (!n.left) return n.right; // 0 or 1 child: lift the child
if (!n.right) return n.left;
let s = n.right;
while (s.left) s = s.left; // 2 children: copy in-order successor
n.val = s.val;
n.right = del(n.right, s.val);
}
return n;
}
function isValidBST(n, lo = -Infinity, hi = Infinity) {
if (!n) return true;
if (n.val <= lo || n.val >= hi) return false; // every node must fit its ancestors' range
return isValidBST(n.left, lo, n.val) && isValidBST(n.right, n.val, hi);
}Traps
- Validating only parent and child is wrong. Each node must fit the range set by all its ancestors.
- Duplicates: decide a rule (ignore, count, or always go right).
In real systems: Database indexes are B+trees: the same idea, but each node holds hundreds of keys so the tree is only 3 or 4 levels deep, which means few disk reads. That's why an index lookup is fast.
Say out loud: It's O(log n) only if it stays balanced. In practice that's a red-black tree, or a B+tree in a database.