Step by step
The example above, written out — the same steps the animation plays.
- 1An empty trie. A trie stores words letter by letter down a tree. Words that share a beginning share the same path.
- 2Insert "car": letter "c". No "c" here yet — create it.
- 3Created "c". New node for "c".
- 4Insert "car": letter "a". No "a" here yet — create it.
- 5Created "a". New node for "ca".
- 6Insert "car": letter "r". No "r" here yet — create it.
- 7Created "r". New node for "car".
- 8"car" stored. Mark the last letter as the end of a word (the ring).
- 9Insert "cart": letter "c". "c" already exists here — follow it (shared prefix "c").
- 10Insert "cart": letter "a". "a" already exists here — follow it (shared prefix "ca").
- 11Insert "cart": letter "r". "r" already exists here — follow it (shared prefix "car").
- 12Insert "cart": letter "t". No "t" here yet — create it.
- 13Created "t". New node for "cart".
- 14"cart" stored. Mark the last letter as the end of a word (the ring).
…and 22 more steps — press Play above to watch them all.
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.