Tries
A tree specialized for prefix operations over strings — each edge is a character, each path from the root is a prefix.
Try answering in your head first, then click a question to check the model answer.
Q1.Why is a trie more efficient than a hash set for autocomplete (finding all words with a given prefix)?(show answer)
A hash set only supports exact-match lookups in O(1) — finding all words with a prefix would require scanning every stored word, O(n · L). A trie lets you walk directly to the node representing the prefix in O(L) time (L = prefix length), then collect all words in the subtree below it — turning a linear scan of the whole dataset into a lookup proportional only to the prefix length plus the number of matches.
Q2.Explain how words with shared prefixes are stored in a trie, using "cat" and "car" as an example.(show answer)
Both words share the path root → 'c' → 'a', reusing the same two nodes. They then diverge: one path continues to 't' (marking end-of-word for "cat"), the other to 'r' (marking end-of-word for "car"). This shared-prefix structure is what makes tries memory-efficient for datasets with many common prefixes, and is exactly what enables fast prefix queries.
Q3.Why does a trie need an explicit "end of word" marker on nodes, rather than just treating leaf nodes as word endings?(show answer)
A word can be a prefix of another longer word stored in the same trie (e.g. "car" and "card") — the node for "car" isn't a leaf, since it has a child continuing to "card," but "car" is still itself a valid, complete word. Without an explicit end-of-word flag, there'd be no way to distinguish "this node represents a complete word" from "this node is just an intermediate prefix on the way to a longer word."
Q4.What's the main downside of a trie compared to a hash set for simple exact-match lookups?(show answer)
A trie's exact-match lookup is O(L) (length of the word) versus a hash set's O(1) average case, and tries generally use more memory per stored item due to the per-character node/pointer overhead — so if you only ever need exact matches (no prefix queries), a hash set is simpler and typically faster/more memory-efficient.