Tries
Intermediate · 16 min read · Problem-Solving Patterns, Greedy & Special Topics
Prefix trees for autocomplete, word search and prefix counting.
A hash set can tell you whether a whole word exists. It can't efficiently tell you which words start with "ca", or whether a partial path through a grid could still become a word. A trie (prefix tree) can. Each node is a character, each root-to-node path spells a prefix, and words that share a prefix share the path.
The structure
Words car, cat, cart, dog:
The template
insert, search and startsWith are all O(L) for a word of length L. Space is O(total characters) in the worst case, with 26 references per node — use a HashMap<Character, Node> for large alphabets.
Wildcard search: branch on .
A normal letter follows one child; a . tries every child — recursion over the trie:
Word Search II: a trie guides the grid search
Running Word Search once per word repeats the same grid exploration for every word. Instead, put all words in a trie and run one backtracking search from each cell that walks the grid and the trie together. The moment the current path isn't a prefix of any word, stop.
Trie or hash set?
Practice ladder
Interview questions
- When would you choose a trie over a hash set of words?
- Why is Word Search II with a trie faster than searching for each word separately?
Further reading
Key takeaways
- A trie stores words as shared prefix paths; operations cost O(word length).
- Mark word ends explicitly; keep pass counts for prefix counting (and don't double-insert).
- . wildcards branch over all children.
- A trie lets one backtracking search look for many words at once, pruning dead prefixes.
- Choose a trie for prefix questions; a hash set for exact lookups only.