What is a trie?
A trie, or prefix tree, stores words letter by letter along paths from the root. Words that begin the same share the same nodes, and a marked node shows where a word ends.
Because a lookup follows one letter at a time, searching for a word takes O(L) for a word of L letters, no matter how many words are stored. That makes tries a good fit for autocomplete, spell checking and prefix search.
Time complexity
| Operation | Time | Notes |
|---|---|---|
| Insert a word | O(L) | One node per new letter |
| Search a word | O(L) | Follow one letter at a time |
| Prefix search | O(L + results) | Walk the prefix, then list below it |
| Delete a word | O(L) | Prune nodes no other word uses |
Try it yourself
- Insert car and then cart and see the shared letters reused.
- Use Starts with and type ca to list every word with that prefix.
- Search a prefix that is not a word and read the message.
- Delete a word and see which nodes are pruned.
Trie vs hash table
A hash table answers exact-match lookups quickly. A trie also answers prefix questions, such as every word that starts with ca, and can list matches in alphabetical order.
Common questions
- What is a trie used for?
- Autocomplete, spell checkers, dictionary lookup and IP routing: anything where matching prefixes matters.
- Why is a trie faster than scanning a list of words?
- The search cost depends only on the length of the word, not on how many words are stored.
- What is the downside of a trie?
- It can use a lot of memory when words share few prefixes, because every letter needs its own node.