Micro-questions over the BST module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The invariant
1. What is a binary search tree?
Answer
A binary tree with an ordering rule — the BST invariant — added on top.
2. State the BST invariant precisely.
Answer
For every node : all values in ‘s left subtree are strictly smaller than , and all values in ‘s right subtree are strictly larger.
3. What is the most common bug when checking the invariant?
Answer
Only checking immediate children. The invariant applies to entire subtrees — a node deep inside the left subtree could still be greater than the root while every parent-child pair looks fine.
4. How do you check the invariant correctly?
Answer
Carry a (low, high) bound down the recursion: every node must satisfy low < node.val < high, with the bound narrowing as you descend. (Equivalently: check that an in-order traversal is strictly increasing.)
5. What does an in-order traversal of a BST produce?
Answer
The values in strictly ascending order. Left → Root → Right walks the tree in sorted order.
B. Searching
6. Describe BST search in four steps.
Answer
- Start at the root.
- If
target == current.val, found. - If
target < current.val, go left — discard the entire right subtree. - Otherwise go right — discard the entire left subtree.
7. What is BST search structurally the same as?
Answer
Binary search on a sorted array — made into a structure rather than an algorithm over one.
8. What makes each comparison worth so much?
Answer
It discards half the remaining tree, not one element. That halving is where comes from.
9. What is the cost of search, stated honestly?
Answer
— the height. Not unless the tree is balanced.
C. The ADT
10. List the BST ADT with costs.
Answer
insert, search, delete, min, max, successor — all ; range(low, high) — for results; in_order() — .
11. How do you find the minimum and maximum?
Answer
Walk left as far as possible for the minimum, right as far as possible for the maximum. A hash map cannot do this at all without checking everything.
12. Why is deletion the fiddliest operation?
Answer
A node with two children cannot simply be removed — it must be replaced by its in-order successor (the smallest value in its right subtree), which is then deleted from where it was.
13. What is range(low, high) and why does it matter?
Answer
Returns every value between two bounds, in . This is the operation databases are built on — WHERE age BETWEEN 20 AND 30.
14. Why are all the costs stated in and not ?
Answer
Because the cost genuinely depends on the height, and the relationship between and is not fixed — it is decided by the shape, which is decided by the insertion order.
D. Height, and why it is not guaranteed
15. What is for a balanced tree, and what does that mean concretely?
Answer
. For a million items that is about 20 comparisons.
16. What is for a degenerate tree?
Answer
. Every operation becomes and the structure is a linked list wearing a tree’s clothes.
17. What input produces a degenerate tree?
Answer
Already-sorted input. Insert 1, 2, 3, 4, 5 and every value goes to the right of the last — a straight line.
18. Why is that catastrophic rather than a curiosity?
Answer
Sorted input is the most common input there is. The worst case is not exotic; it is the default. Which is why unbalanced BSTs are essentially never used in production.
E. Self-balancing
19. What do self-balancing trees do to keep at ?
Answer
Tree rotations — local rearrangements that reduce height while preserving the BST invariant.
20. What does a right rotation do?
Answer
Lifts the left child into the parent’s position and pushes the parent down to the right, reattaching the middle subtree. Order is preserved; height on the heavy side drops by one.
21. What balance rule does an AVL tree enforce, and what is it best for?
Answer
Height difference between left and right subtrees at every node — strict. Best for read-heavy workloads where lookup speed is critical.
22. What rule does a red-black tree enforce instead?
Answer
Node colours and rules ensuring the longest path is at most the shortest. Looser, so it needs fewer rotations on insert and delete.
23. Where are red-black trees used in the real world?
Answer
Java TreeMap, C++ std::map, and the Linux kernel process scheduler.
24. What do B-trees and B+ trees change, and why?
Answer
Nodes hold hundreds of keys and have hundreds of children instead of two. This cuts the height to 3–4 levels for billions of records, minimising expensive disk reads/seeks.
25. Where are B-trees used?
Answer
Every major database index (PostgreSQL, MySQL InnoDB, SQLite) and filesystems (ext4, NTFS).
26. Complete the complexity table: unbalanced BST vs AVL vs red-black, average and worst case.
Answer
| Average search | Worst search | |
|---|---|---|
| Unbalanced BST | ||
| AVL | ||
| Red-black |
The whole value of self-balancing is in the second column.
F. BST versus hash map
27. Which is faster for search, insert and delete?
Answer
A hash map — average versus . But the tree’s is guaranteed and the hash map’s is not.
28. Cost of min/max in each?
Answer
Hash map: — you must check everything. Balanced BST: .
29. Cost of a range query in each?
Answer
Hash map: not possible without a full scan. Balanced BST: .
30. Cost of getting everything in sorted order?
Answer
Hash map: — you have to sort it. BST: — just traverse in order.
31. Worst case of each?
Answer
Hash map: (collisions or an adversary). Balanced BST: .
32. Summarise the choice in one sentence.
Answer
A hash map is faster on average for the operations it supports; a balanced tree is slower but guaranteed, and it keeps the ordering that hashing throws away.
33. Why is a database index a B-tree and not a hash index?
Answer
Because WHERE age BETWEEN 20 AND 30 is a range query, and a hash index simply cannot answer it.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Binary Search Trees — the module
- Binary Trees — Question Bank — the previous bank
- Hash Maps — Question Bank — the structure this one is contrasted with
- Tree Traversal — where in-order is done properly
Software engineering
Infrastructure & security
Computer science
Hardware & engineering