Binary Search Tree Search
Binary search made dynamic — one ordering comparison per level steers you left or right, and the structure absorbs inserts and deletes that would cripple a sorted array.
Hands on Interactive visualization
Implementation Code
interface Node {
key: number;
left: Node | null;
right: Node | null;
}
// Iterative descent — O(height), O(1) space.
export function bstSearch(root: Node | null, key: number): Node | null {
let cur = root;
while (cur !== null) {
if (key === cur.key) return cur; // found
// one comparison discards an entire subtree
cur = key < cur.key ? cur.left : cur.right;
}
return null; // fell off a leaf: not present
}Big-O Complexity
O(log n) holds only while the tree stays balanced; a degenerate tree (e.g. built from sorted inserts) is a linked list with O(n) search. Self-balancing variants — red-black (std::map, Java TreeMap), AVL, B-trees — guarantee O(log n) worst case. Iterative descent is O(1) space; recursion costs the tree height.
In production When to use
C++ std::map/std::set (red-black trees) and Java's TreeMap/TreeSet keep keys sorted while supporting O(log n) insert, delete, and search — the go-to when you need a mutable dictionary that stays ordered.
Find all keys in [a, b] falls out naturally: descend to the boundary, then walk in-order — O(log n + k) for k results. A hash table cannot answer this at all without scanning everything.
Largest key ≤ x and smallest key ≥ x are one root-to-leaf descent, recording the best candidate at each turn — the backbone of rate limiters, calendar slot finders, and TreeMap.floorKey/ceilingKey.
In-order traversal yields all keys in sorted order in O(n) with no separate sort step — leaderboards, ordered dumps, and merge-style operations get sorted output for free.
B-trees and B+ trees — the wide, disk-friendly cousins of the BST — power nearly every relational database index and many filesystems, using the same ordered-descent search per node.
Order books, schedulers, and interval trackers that need min/max, arbitrary delete, AND membership in log time use balanced BSTs where a heap (no arbitrary lookup) falls short.
Trade-offs Strengths & weaknesses
- O(log n) search, insert, AND delete when balanced — the sorted array only matches the search.
- Keys stay in sorted order: range queries, floor/ceiling, min/max, and ordered iteration come built in.
- Self-balancing variants (red-black, AVL) make O(log n) a worst-case guarantee, not a hope.
- In-order traversal produces sorted output in O(n).
- Predecessor/successor navigation in O(log n) — the operations hash tables fundamentally can't do.
- No resizing or rehashing pauses; cost is smooth per operation.
- A plain BST degrades to O(n) on sorted or adversarial insert orders — balancing is not optional in production.
- Slower than hash tables for pure equality lookup: O(log n) with a comparison per level vs expected O(1).
- Per-node pointer overhead and scattered allocations are cache-hostile next to a flat sorted array.
- Deletion (the two-children case) and rebalancing rotations are fiddly to implement correctly.
- Requires a total order on keys — and the comparator must be consistent, or the structure silently corrupts.
Intuition Mental model
Twenty questions on ordered data
Playing 20 questions with is it bigger or smaller?: each answer eliminates one entire subtree from consideration. A well-built tree halves the candidates per question — but if the questions were arranged badly (a degenerate tree), you're reduced to asking about candidates one at a time.
- Start at the root question = compare the target with the root key.
- Smaller sends you down the left branch, bigger down the right = one comparison discards a whole subtree.
- Each level is another question; a balanced tree of a million keys needs about 20 = O(log n).
- Reaching a question with no follow-up (a null child) = the key is not in the tree.
- A quiz where every answer leads to just one more question in a long chain = the degenerate tree: 20 questions becomes n questions.
Prep Interview questions
Validate that a binary tree is a BST. What's the classic wrong answer?
Find the k-th smallest element in a BST.
Find the floor of x (largest key ≤ x) in one descent.
Why does inserting sorted data destroy a plain BST, and what fixes it?
Delete a node with two children from a BST.
Watch out Common bugs
Feeding ascending keys into a plain BST chains every node down the right spine: height n, search O(n). It passes small tests and collapses on real data. Use a self-balancing tree, or detect that your input is presorted and build by midpoint instead.
The tree is organized by its comparator; if equals() disagrees with compare() == 0 (Java's TreeMap docs warn exactly this), lookups descend to the wrong subtree and 'contained' keys go unfound. All navigation — search, insert, delete — must use the one comparator.
Deciding ad hoc whether duplicates go left, right, or get rejected leads to inconsistent trees where count queries and deletes misbehave. Pick one policy up front: reject, keep a count field per node, or store a list of values per key.
The two-children delete swaps in the in-order successor; forgetting to reattach the successor's own right child to the successor's parent silently drops a whole subtree. Draw the three cases (leaf, one child, two children) before coding.
One screen Cheat sheet
Compare at each node, go left if smaller, right if bigger — binary search over a linked structure that also supports fast inserts.
- O(log n) only while balanced; sorted inserts degrade a plain BST to a linked list.
- Self-balancing variants guarantee log n: red-black (std::map, TreeMap), AVL, B-trees on disk.
- In-order traversal = sorted order; validates the tree and powers ordered iteration.
- Floor/ceiling: record best-so-far during a single descent, no backtracking.
- All navigation must use one comparator — equals() disagreeing with compare() corrupts lookups.
- Decide the duplicate policy up front: reject, count field, or bucket per key.