A paper dictionary. You're looking for "mango". You open somewhere in the middle and land on "kite". Without reading a single other word, you already know something huge: mango is after this page. Half the dictionary — eliminated by one glance. Repeat, and a 1,000-page dictionary surrenders its word in about ten opens.
Why did that work? Only because the dictionary is sorted. Now the engineering question of this lesson: yesterday you learned trees; earlier you learned that sorted arrays search fast but insert slowly (everything shifts). Can we build sortedness INTO a tree's shape — so lookups get the dictionary trick, while inserts stay cheap pointer surgery?
Yes. It's called a binary search tree, and it needs exactly one rule.
One rule, taken seriously
A binary search tree is a binary tree with one invariant:
Everything in a node's LEFT subtree is smaller than the node; everything in its RIGHT subtree is larger.
Read it once more, with the stress where it belongs: everything in the subtree — not just the immediate children. A node three levels down in the right subtree of 50 must still be greater than 50; every ancestor's comparison constrains every descendant below it.
"Isn't that the same thing as 'left child smaller, right child bigger'?" It is not, and the difference is a famous trap. Picture: root 10, right child 15, and 15 has a left child 6. Check parent-child pairs: 15 > 10 ✓, 6 < 15 ✓ — all local checks pass. But 6 sits in the right subtree of 10 while being smaller than 10 — the tree is NOT a valid BST, and any search for 6 (which goes left at 10) will never find it. Hold this example; it decides the validate-BST question in your Practice Zone.
Search: the dictionary trick on a tree
With the rule in place, searching writes itself. Standing at any node, one comparison tells you everything:
def search(node, target):
while node:
if target == node.val:
return node # found it
if target < node.val:
node = node.left # rule says: it can ONLY be left
else:
node = node.right # it can ONLY be right
return None # fell off: not presentNotice what each comparison does: it doesn't just pick a direction — it discards an entire subtree, every node in it, unexamined. That's the dictionary glance. One comparison per level, so the total cost is the height of the tree. Bushy tree of 10 lakh nodes → height ≈ 20 (lesson 6's doubling fact) → ~20 comparisons.
Dry run: finding 60
tree: 50 at root; 30, 70 below; 20, 40, 60, 80 below them search(60): at 50: 60 > 50 -> go RIGHT (20, 30, 40 discarded, unseen) at 70: 60 < 70 -> go LEFT (80 discarded) at 60: found. 3 comparisons for 7 nodes.
Seven nodes, three looks — and the entire left half of the tree was never touched. Feel the scale: a linear scan of 10 lakh IDs averages 5 lakh looks; a bushy BST needs ~20.
Insert: search until you fall off
Where does a new value go? Try inserting 65 into the tree above, by hand. You must keep the rule intact, so... follow the same comparisons as a search: 65 > 50 go right, 65 < 70 go left, 65 > 60 go right — and there is nothing there. That empty spot is exactly where 65 belongs.
def insert(node, val):
if node is None:
return Node(val) # fell off: plant it here
if val < node.val:
node.left = insert(node.left, val)
elif val > node.val:
node.right = insert(node.right, val)
return node # (duplicates: ignored here)Insert = search + plant at the point of falling off. Cost: one walk down, O(height). And notice something that will matter enormously in a moment: where a value lands depends entirely on what was inserted before it.
A free gift: sorted order
Remember inorder traversal from lesson 6 — left, node, right? Predict what it prints on a BST before running it.
def inorder(node, out):
if node:
inorder(node.left, out)
out.append(node.val)
inorder(node.right, out)
return out
# tree built from: 50, 30, 70, 20, 40, 60, 80
print(inorder(root, []))Result
[20, 30, 40, 50, 60, 70, 80]
Sorted. Always, for any valid BST — because at every node, everything smaller is printed before it and everything larger after it, recursively. Two practical corollaries fall out for free: k-th smallest = inorder, stop at the k-th visit; and validate a BST = inorder, check the output is strictly increasing. A structure that stays sorted while accepting cheap inserts — that's the whole promise delivered.
Delete: the three cases
Deletion is the only fiddly operation, and it splits by how many children the victim has. Cases 1 and 2 are easy; think about why case 3 can't be:
Case 1 — a leaf: unlink it. Done. Case 2 — one child: the child takes the victim's place (grandparent adopts grandchild). Still easy.
Case 3 — two children: now removing the node orphans TWO subtrees, and only one pointer slot waits above. We can't remove the node — so we replace its value. With what? It must be bigger than everything in the left subtree and smaller than everything in the right — the value just above the deleted one: the smallest value in the right subtree, called the inorder successor.
And here's the elegant part: that successor, being the smallest of its subtree, cannot have a left child — so deleting it from its old position is case 1 or case 2. The hard case reduces itself to an easy one, by construction. (The mirror choice — largest of the left subtree — works identically.)
The trap: sorted input kills the tree
Now the moment this lesson has been building toward. Take an empty BST and insert 1, 2, 3, 4, 5 — in that order. Draw it before looking.
Every new value is larger than everything present, so every insert goes right, and right, and right. The "tree" is a linked list wearing a tree costume — height n−1, search O(n). Every logarithmic promise: void.
And here's why this is a real problem and not a curiosity: sorted input is not rare bad luck — it's the most common input there is. Auto-increment IDs, timestamps, roll numbers — real data loves arriving in order. Feed production data to a plain BST and it will quietly degenerate. This is why honest complexity tables say O(log n) average and O(n) worst — and why the next section exists.
🎯 Selection-round radar: "what happens if you insert sorted data into a BST?" is the single most-reported BST theory question. Four beats: the shape (right-leaning chain), the cost (O(n)), why it's common (IDs, timestamps), the fix (self-balancing trees). Fifteen seconds, full marks.
The fix: self-balancing trees
If lopsidedness is the disease, the cure is surgery on the way in: self-balancing BSTs (AVL trees, red-black trees) detect when an insert has made the tree lopsided and repair it with rotations — local pointer moves that lift the middle value up and hang the other two off it:
# the smallest rescue: inserting 1, 2, 3
#
# 1 2
# \ rotate / \
# 2 -------> 1 3
# \
# 3
# chain of height 2 -> perfect tree of height 1
# same values, same BST rule, shorter pathsCheck for yourself: the rotated tree still satisfies the BST rule (1 < 2 < 3), and the longest path shrank. A rotation is O(1) pointer work; a few per insert keep the height at O(log n) guaranteed — the promise a plain BST can't make.
At placement level you need the contract, not the case analysis: AVL keeps left/right heights within 1 (stricter → faster lookups, more rotation work); red-black tolerates ~2× imbalance (looser → cheaper inserts — the default inside C++ std::map and Java TreeMap). Both: O(log n) worst case for search, insert, delete.
What if...?
What if I insert a duplicate? Policy, not law — three respectable options: reject it, keep a count field on the node, or send equals consistently to one side. What interviewers check is that you state a policy rather than let one happen by accident of your comparison operator.
What if the tree is empty? Search returns None immediately; insert plants the root. The node is None base case covers both — the empty tree is never a special case if your base case is honest.
What if I only ever do exact-key lookups — no ranges, no sorted output? Then a hash table is simpler and faster, and choosing the BST anyway is structure-for-structure's-sake. The BST earns its keep on ordered questions: ranges ("marks between 80 and 90"), nearest key, min/max, k-th smallest, sorted iteration — things hashing's scattering can never answer.
What if I need guaranteed bounds in production? Use the library's balanced tree (TreeMap, std::map) — nobody hand-rolls AVL at work. In interviews, hand-rolled plain BST + knowing the degeneration story + naming the balanced fix is the expected package.
Common mistakes
- Validating a BST by checking only parents against children — the 10/15/6 counterexample above defeats it; carry (min, max) bounds down instead.
- Claiming O(log n) unconditionally — the honest cost is O(height), and only balance makes height logarithmic.
- Deleting a two-child node by promoting one child directly — orphans the other subtree; use the inorder successor.
- No stated duplicates policy.
- Using a BST for pure exact-key lookups — a hash table is the better tool; the tree is for ordered queries.
- Forgetting that insertion ORDER shapes the tree — same values, different order, different tree.
How do I recognise BST problems?
- "range / between / floor / ceiling / nearest / k-th smallest / sorted order" while data keeps changing → BST territory (a static sorted array + binary search handles the frozen version).
- "validate this BST" → bounds-passing recursion, or inorder-is-increasing.
- Any question inside a given BST → exploit the rule to discard subtrees; if your solution touches every node, you probably ignored the rule (e.g. LCA in a BST is a guided O(h) walk, not a search).
Quick revision
| Operation | Balanced | Degenerated (worst) | Space |
|---|---|---|---|
| Search | O(log n) | O(n) | O(1) iterative |
| Insert / delete | O(log n) | O(n) | O(height) recursion |
| Inorder traversal | O(n) — always yields sorted order | O(height) | |
| AVL / red-black | O(log n) guaranteed | rotations O(1) each | |
When the worst bites: sorted or nearly-sorted insertion — IDs, timestamps — the most ordinary data there is.
One thing to remember
A BST is the dictionary trick built into a tree: every comparison discards a whole subtree — but the trick only works while the tree stays bushy, and sorted input makes it a chain.
Practice Zone — PYQs from real selection rounds
Six MCQs, then three tasks: build a BST by hand, count search comparisons, and write the bounds-based validator that survives the 10/15/6 trap.
The binary search tree rule is:
Asked in
Searching a BALANCED BST of 10,00,000 nodes takes about how many comparisons?
Asked in
Which traversal of a BST visits values in sorted ascending order?
Asked in
Inserting 1, 2, 3, 4, 5 into an empty BST in that order produces:
Asked in
Deleting a node with TWO children from a BST works by:
Asked in
This 'validate BST' code is buggy: it only checks node.left.val < node.val < node.right.val at each node. What tree exposes the bug?
Asked in
Hands-on tasks:
Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST in that order. Draw the result (as text), then state its inorder traversal without walking the tree.
Asked in
Write BST search and count how many comparisons it makes finding 60 in the tree built from 50, 30, 70, 20, 40, 60, 80.
Asked in
Write the correct validate-BST using (min, max) bounds, and show why it rejects: root 10, left 5, right 15, where 15 has left child 6.
Asked in
FAQ
BST vs binary search on a sorted array — same log n, so why both?
Same halving idea, different medium. The sorted array searches in O(log n) but pays O(n) per insert (everything shifts — lesson 2). The BST does both in O(log n) when balanced. Static data → sorted array. Data that changes while you query it → tree.
Do real databases use BSTs for indexes?
The idea, not the binary version. Disks read in blocks, so databases use B-trees / B+ trees — search trees whose nodes hold hundreds of keys each, making a billion rows only 3–4 levels deep. Binary in RAM, B-tree on disk — same ordering principle, branching factor tuned to the medium.
Should I memorise the AVL rotation cases (LL, LR, RL, RR)?
For placements: know why rotations exist, what one does (lift the middle of three; O(1) pointer changes), and the AVL vs red-black contract difference. The four-case choreography is rarely asked outside specialised rounds — understanding beats recitation here.
How do I find the k-th smallest element efficiently?
Inorder traversal, stopping at the k-th visit — O(h + k) with an explicit stack. (It's a Google favourite; the full traced version is on the Google company page.) If k-th queries dominate the workload, augment nodes with subtree sizes for O(log n) per query.
Ordered and dynamic — that's the BST's niche. Next, a tree that gives up almost all order to answer one question instantly: "what's most urgent?" — Lesson 8: Heaps & Priority Queues →