Tries
Prefix trees for efficient string operations
What Makes Tries Special
A Trie (pronounced "try") is a tree where each node represents a character. Words share common prefixes, making prefix operations incredibly efficient. Perfect for autocomplete, spell checkers, and IP routing tables.
Key Benefits
- • O(m) search where m = word length
- • Prefix matching in O(p + k) time
- • Space-efficient for shared prefixes
- • Alphabetical ordering for free
Use Cases
- • Autocomplete / typeahead
- • Spell checking
- • IP routing (longest prefix match)
- • Word games (Scrabble, Boggle)
Autocomplete Demo
Add New Word
Words in Trie (12)
appappleapplicationapplybananabandbandanacarcardcarecarefulcat
Trie Structure
(root)
└a
└p
└p*
└l
└e*
└i
└c
└a
└t
└i
└o
└n*
└y*
└b
└a
└n
└a
└n
└a*
└d*
└a
└n
└a*
└c
└a
└t*
└r*
└d*
└e*
└f
└u
└l*
*End of word
Current search path
Complexity Analysis
| Operation | Trie | Hash Set | Notes |
|---|---|---|---|
| Insert word | O(m) | O(m) | m = word length |
| Search word | O(m) | O(m) | Same for exact match |
| Prefix search | O(m + k) | O(n) | Trie wins! m = prefix, k = matches |
| Space | O(n×m) | O(n×m) | Trie shares prefixes, often less in practice |
Tries excel at prefix-based operations. For pure exact-match lookup, hash tables are simpler and equally fast.