Question 1

Why do trees need balancing?

Accepted Answer

Start from the problem, not the solution: "A plain BST does not balance itself — its shape depends entirely on insertion order. With sorted data every new element goes down the right branch and the tree becomes a linked list: h = n, all operations O(n)." Then make it real: "This is not an exotic case. Auto-increment IDs, timestamps, an already-sorted export — real data often arrives exactly like this." Show a number, because numbers stick: "For a million elements the difference is 20 comparisons versus a million." Then the solution in one sentence: "Self-balancing trees — AVL, Red-Black — restore the shape with rotations after each insert/delete and provide the GUARANTEE h = O(log n). A rotation is O(1) and does not change the inorder order, so the BST invariant holds." Tie it back to the real world to close: "Java/Kotlin's TreeMap and C++'s std::map are red-black trees; database indexes use B-trees, the same idea adapted for disk."

Question 2

What is a rotation and what does it do?

Accepted Answer

Explain a rotation as a picture, not as pointer manipulation — that is what interviewers want. "A rotation is a local restructuring of a subtree. Say a node leans right — its right subtree is taller than its left. A left rotation lifts the right child up and makes the old parent its left child. The tall branch drops a level, the short branch rises a level, and the tree flattens." Then list three facts — together they complete the answer: Inorder order is unchanged. The relative order of elements stays the same, so the BST invariant is automatically preserved. This is why a rotation is safe. It is O(1). Only a few pointers move; no subtree is traversed. There are four cases — LL, RR, LR, RL. LL and RR are fixed with one rotation; LR and RL need two in sequence (rotate the child first, then the parent). Wrap up with complexity: after an insert the balance check may propagate to the root, i.e. at worst O(log n) — so the insert as a whole stays O(log n). Saying you do not know the exact code by heart is not a weakness: "I would not write the precise pointer sequence from memory, but I can explain the principle and when it applies" is a perfectly acceptable answer.

Question 3

Compare AVL and Red-Black trees. When would you pick each?

Accepted Answer

Derive the difference from the balance condition — everything else follows from it. "AVL imposes a strict condition: at every node the height difference between subtrees is at most 1. Red-Black keeps a looser condition via colour rules — the longest path may be at most twice the shortest." Then list the consequences: "Because AVL is stricter, the tree is shallower and search is slightly faster. But maintaining that shape takes more rotations, making insert and delete costlier. Red-Black is the reverse: a somewhat taller tree, but cheap writes." Give the selection rule concretely: "Read-heavy workloads favour AVL; write- and delete-heavy workloads favour Red-Black. Both give the same asymptotics — search, insert, delete all O(log n) — the difference is in constant factors." Add real usage, since it grounds the answer: "In practice Red-Black is far more widespread — Java/Kotlin's TreeMap and TreeSet, C++'s std::map, the Linux kernel scheduler. The reason is that general-purpose collections carry a serious write load too." And the final, most important sentence: "In a real project I almost never make this choice — I take the standard library's structure. It only becomes relevant when writing your own structure or when you have a very specific performance profile."

Question 4

What do you do if you are asked to implement an AVL tree?

Accepted Answer

This is a question about honesty and self-assessment. Improvising half-correct rotation code is the worst option — the interviewer spots the error immediately. Structure the strong answer like this: 1. State the boundary honestly: "I could not write the exact pointer sequence for the rotations from memory — I have never hand-written one in practice." 2. Explain the principle so your understanding shows: "But I know the algorithm: do a normal BST insert, then walk back up the modified path recomputing each node's balance factor — the difference between left and right heights. At the first node where |difference| > 1, identify one of four cases: LL, RR, LR, RL. LL and RR need one rotation, LR and RL need two in sequence." 3. Offer what you can write: "If you like, I can write the simple right rotation and the balance-factor computation." This steers the question toward the part you can do. 4. Show the practical choice: "In production I would not write this — I take TreeMap, SplayTreeMap or std::map. My own implementation would not beat a battle-tested library, and the deletion cases are easy to get wrong." That answer demonstrates three qualities: honesty, understanding of the mechanism, and engineering judgement. At middle level it is the ideal answer — because that is exactly what is expected.

Question 5

Why do database indexes use B-trees rather than AVL/Red-Black trees?

Accepted Answer

The key to this answer is the memory hierarchy — looking purely at asymptotics leaves the question unanswered, since both are O(log n). "The difference is that disk (or SSD) reads happen in blocks — 4 KB or 8 KB, say. Reading one byte costs about the same as reading four kilobytes. So the real cost is not the operation count but the number of disk reads." Then draw the conclusion: "In a binary tree each node holds one key and each level means one disk read. For a million keys h ≈ 20, so 20 disk reads. In a B-tree each node holds hundreds of keys — one whole block is read at a time. For the same million keys the height is 3–4, so only 3–4 disk reads. That is roughly a fivefold difference." List the additional reasons: in a B+tree all data lives at the leaf level and the leaves are linked together, so a range scan (WHERE date BETWEEN ...) becomes a sequential read — the fastest pattern for a disk. And because node size is matched to the block size, memory pages are used efficiently too. Name the general principle — this lifts the answer to senior level: "Choosing a data structure is not only about asymptotics; the memory hierarchy and the size of the access unit are often more decisive. By the same logic, cache locality dramatically changes the constant factors of in-memory structures too."

Property	AVL	Red-Black
Balance condition	Height difference between subtrees is at most 1 at every node	Colour rules; the longest path is at most twice the shortest
How balanced	Stricter — the tree is shallower	Looser — the tree can be somewhat taller
Search	Slightly faster (shallower tree)	Slightly slower
Insert / delete	More rotations — costlier	Fewer rotations — cheaper
When it wins	Read-heavy workloads	Write-heavy workloads
Where it is used	Some DB indexes, in-memory indexes	Java/Kotlin `TreeMap`/`TreeSet`, C++ `std::map`, the Linux scheduler

Balancing: AVL and Red-Black

📚 Sources and documentation