Unit 5 · Heavy
Ordering that supports fast search, but only while the shape stays balanced. The caveat is the unit, and self-balancing structures exist entirely to enforce it.
What a strong answer looks like
A strong Unit 5 answer states the ordering property over whole subtrees and names the shape assumption behind any complexity it quotes.
Know
In-order yields sorted output on a search tree; pre-order suits copying; post-order suits deletion; level-order needs a queue.
Apply
Pick the traversal from the task rather than by habit.
Watch out
Deleting pre-order, which frees a parent whose children are still reachable only through it.
Study move
Write all four traversals of one tree and say which is sorted.
Know
The ordering property constrains entire subtrees, not just immediate children, which is what allows discarding half the tree per step.
Apply
Validate the property recursively, carrying bounds down the tree.
Watch out
Checking only parent against children, which accepts invalid trees.
Study move
Build a tree where every parent-child pair is ordered but the tree is not a valid BST.
Know
Inserting sorted keys degenerates a plain BST into a chain, turning logarithmic search linear. AVL and red-black trees restore balance by rotation.
Apply
Quote logarithmic search only alongside the balance assumption.
Watch out
Assuming a BST is balanced. Nothing enforces it unless the structure is self-balancing.
Study move
Insert 1 through 7 in order and describe the resulting shape and cost.
Know
A trie indexes by prefix, making prefix queries proportional to key length rather than to the number of keys. Segment trees answer range queries on changing data.
Apply
Use a trie for prefix work and a segment tree when ranges must be queried and updated.
Watch out
Using a prefix array on data that changes, where a segment tree is the right structure.
Study move
Say which structure fits autocomplete and which fits a mutable range sum.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Write a validator for a binary search tree that carries bounds downward, and explain why local comparison is insufficient.
