Lesson 20
Binary Search Trees
Keep smaller values left and larger values right — and search becomes O(log n).
01Why it matters & the intuition
BSTs combine the fast search of a sorted array with fast insertion of a linked list. Balanced variants (red-black, AVL, B-trees) power TreeMap, database indexes and file systems.
Think of it like…
A '20 questions' game where every question is 'is it smaller than X?'. Each answer sends you left or right, discarding a whole subtree — like binary search, but the structure stays cheap to update.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- path
- done / found / visited
- removing
- successor
03Key ideas
BST property
For every node: all values in its left subtree are smaller, all values in its right subtree are larger. Not just the direct children — the whole subtree.
Search & insert
Compare with the current node, go left or right, repeat. Insert where you fall off the tree.
Delete
Leaf: remove it. One child: splice it out. Two children: replace the value with the in-order successor (smallest in the right subtree), then delete that successor.
Balance matters
Inserting sorted data builds a linked list of height n: O(n) operations. Self-balancing trees rotate to keep height O(log n).
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
class BST {
root: TreeNode | null = null;
insert(value: number): void {
const node = new TreeNode(value);
if (!this.root) { this.root = node; return; }
let cur = this.root;
while (true) {
if (value === cur.value) return; // no duplicates
const side = value < cur.value ? "left" : "right";
if (!cur[side]) { cur[side] = node; return; }
cur = cur[side]!;
}
}
has(value: number): boolean {
let cur = this.root;
while (cur) {
if (value === cur.value) return true;
cur = value < cur.value ? cur.left : cur.right;
}
return false;
}
remove(value: number): void {
this.root = this.removeFrom(this.root, value);
}
private removeFrom(node: TreeNode | null, value: number): TreeNode | null {
if (!node) return null;
if (value < node.value) node.left = this.removeFrom(node.left, value);
else if (value > node.value) node.right = this.removeFrom(node.right, value);
else {
if (!node.left) return node.right; // 0 or 1 child: splice out
if (!node.right) return node.left;
let succ = node.right;
while (succ.left) succ = succ.left; // in-order successor
node.value = succ.value;
node.right = this.removeFrom(node.right, succ.value);
}
return node;
}
}05Complexity
| Operation | Time | |
|---|---|---|
| Search / insert / delete (balanced) | O(log n) | — |
| Search / insert / delete (degenerate) | O(n) | — |
| In-order walk (sorted output) | O(n) | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Validate a BST
Write is_valid_bst(root) returning true if the tree satisfies the strict BST property (no duplicates). Nodes are { value, left, right }.
Nodes have .value, .left and .right.