What a binary search tree is
You're keeping a live game leaderboard. Scores arrive nonstop, and the UI keeps asking ordered questions: is 4,200 on the board? What's the closest score below 5,000? From the Binary Trees lesson you know a sorted array answers fast (
O(log n) binary search) but pays O(n) per insert — everything shifts. An unsorted list inserts free but answers slow. You need both fast, forever.A binary search tree (BST) is a binary tree with one promise — the invariant — kept at every node:
- everything in the left subtree is smaller than the node
- everything in the right subtree is larger
Not just the direct children — the entire subtrees. That's what makes a comparison so powerful: standing at the root and comparing once tells you which whole half of the tree your value cannot be in. The figure shows the tree built from
6, 2, 8, 0, 4 — check the promise at each node before moving on.6
2
8
0
4
Quick check
In a BST, the value 7 is compared against the root 6. Predict what one comparison buys you.
Answer it in the interactive lesson to keep your progress.
The core operations
Every BST move is the same downward walk, steered by comparisons:
- search(target) — compare at the node: smaller → go left, larger → go right, equal → found. Falling off the tree (
null) means not here. - insert(val) — the same walk, and the spot where you fall off is exactly where the new node belongs. No shifting, ever.
- min / max — walk as far left (or right) as possible; the invariant guarantees the extreme lives at the end.
Build the example tree by inserting
6, 2, 8, 0, 4 one at a time. Watch how each value's walk decides its home: 2 goes left of 6; 4 goes left of 6, then right of 2 — two comparisons, placed:function makeNode(val) {
return { val, left: null, right: null };
}
function insert(root, val) {
if (!root) return makeNode(val); // fell off — this is the spot
if (val < root.val) root.left = insert(root.left, val);
else root.right = insert(root.right, val);
return root;
}
let root = null;
for (const v of [6, 2, 8, 0, 4]) root = insert(root, v);
console.log(root.val); // 6
console.log(root.left.val); // 2
console.log(root.left.right.val); // 4Quick check
Inserting 3 into the tree built from [6, 2, 8, 0, 4]: predict its walk.
Answer it in the interactive lesson to keep your progress.
Your first BST problem: the floor (closest value ≤ target)
The leaderboard question: what's the closest score at or below 5? On the tree from
[6, 2, 8, 0, 4] the answer is 4. A scan checks everything; the invariant answers in one walk.The steps
- Keep a
bestanswer, starting at-1(nothing found yet). - At each node: an exact match wins immediately.
- If the node is too big (
> target), it can't be the floor — and neither can anything to its right. Go left. - If the node fits (
≤ target), it's a candidate — remember it inbest, then go right to look for a bigger one that still fits. - Falling off the tree ends the walk;
bestholds the floor.
Trace it — floor(5)
- at
6: too big → go left (best still-1) - at
2: fits →best = 2, go right for something bigger - at
4: fits →best = 4, go right - right of
4isnull— done. Floor is 4.
In the animation, first watch the inserts reuse the walk you just learned, then watch the search: at every step one entire subtree fades out — count the comparisons (three) against the five values stored. In JavaScript, the floor walk:
This section has a step-by-step animation in the interactive lesson.
function floorBST(root, target) {
let best = -1;
let node = root;
while (node) {
if (node.val === target) return node.val;
if (node.val < target) {
best = node.val; // fits — remember it, try bigger
node = node.right;
} else {
node = node.left; // too big — floor must be left
}
}
return best;
}
console.log(floorBST(root, 5)); // 4
console.log(floorBST(root, 7)); // 6Quick check
floor(1) on the same tree — predict the walk and answer.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Sorted inserts build a list. Insert
1, 2, 3, 4, 5in order and every node goes right — the "tree" is a straight line and every operation isO(n). Real systems use self-balancing trees (AVL, red-black) that rotate nodes to keep the height nearlog n; the invariant and the walks you just learned are unchanged there. - Validating pairs instead of subtrees. Checking only
left.val < node.val > right.valat each node misses deep violations — a7buried bottom-left of a root5passes every local check but breaks the tree. Validation must carry bounds down the recursion (this topic's Level-2 challenge). - Dropping the returned root. With the recursive insert, forgetting
root = insert(root, v)on an empty tree throws the new node away. - Duplicates. Decide a policy up front — reject them, count them in the node, or send them consistently to one side. Mixing policies corrupts ordered walks.
Quick check
Values [1, 2, 3, 4, 5] are inserted in that order into a plain BST. Predict the cost of searching for 5.
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, every operation is one root-downward walk, so everything is priced by the height:
| Operation | Balanced (height ≈ log n) | Degenerate (height = n) |
|---|---|---|
| search / insert / floor | O(log n) | O(n) |
| min / max | O(log n) | O(n) |
| in-order traversal | O(n) | O(n) |
Storing
n nodes takes O(n) space; recursion adds O(height) stack.Key takeaways:
- One invariant — left smaller, right larger, for whole subtrees — powers every operation.
- Search, insert, and floor are all the same walk with different bookkeeping.
- Balance is everything: sorted inserts degrade to
O(n); self-balancing trees fix it. - In-order traversal reads a BST in sorted order — free sorting from structure.
These classics build straight on this walk, each its own lesson later (no need to know them yet): validate a BST (bounds down the recursion — the Level-2 challenge here), lowest common ancestor (walk until the targets split — the second animation in See it), k-th smallest (in-order with a counter), and delete a node (splice in the in-order successor). Next up in order: Heaps — a tree kept just ordered enough to always hand back the smallest (or largest) item first.