What's happening?
- Inserting a word follows existing letters and creates new nodes only where the word differs.
- The node for a word's last letter is marked as the end of a word.
- To autocomplete, follow the prefix, then collect every word in the subtree below it.
Complexity
- Time
- O(L) to insert or look up a word of length L — however many words are stored
- Space
- Up to one node per letter stored
Where you'll meet it
Search-box autocomplete, spell checkers, IP routing tables (longest-prefix match), and word games.
Common mistake
Forgetting the end-of-word mark: without it, storing "cart" would make "car" look like a word too.
FAQ
Why is lookup independent of how many words there are?
You only ever walk down as many levels as the word has letters.
Trie vs hash map?
A hash map answers "is this exact word here?" just as fast, but cannot list every word with a given prefix.
Don't tries use a lot of memory?
They can. Compressed tries (radix trees) merge chains of single children to save space.