Algorithms from zero
Trees: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes the structure stick.
Reconstruct the unit’s spine — why recursion fits a tree, what the three DFS orders are for, the BST invariant and the balance caveat, when BFS beats DFS, and the tree-DP pattern — without looking back at the lessons.
- 01Why is recursion the natural way to process a binary tree?
- 02Name the three depth-first traversal orders and what each is for.
- 03State the BST invariant and what it buys you.
- 04Why does O(h) not always mean O(log n) for a BST, and what is the worst case?
- 05When do you choose level-order (BFS) over a depth-first traversal, and what makes it work?
- 06Describe the tree-DP pattern and why the return value differs from the answer.
If you could reconstruct each answer from memory, you hold the unit’s spine: a binary tree is recursively defined, so recursion (solve subtrees, combine with the node) is the universal template; the three DFS orders differ only in when the node is visited, and in-order reads a BST out sorted; the BST invariant buys O(h) operations but only balance keeps h near log n; BFS with a queue and a per-level size snapshot is the tool when depth matters; and tree DP returns extendable local info up while accumulating the true global answer on the side.