Tries
The problem
Searching for all words with a given prefix, or checking whether any stored string starts with a given sequence, is awkward and slow with a hash table — a hash table can only tell you if an exact string exists, not efficiently enumerate everything sharing a prefix.
Why now
Trees already gave the general branching structure; hash tables already gave fast exact-match lookup for strings. A trie is what you get by organizing strings char-by-char down a tree instead of hashing them whole — trading hash tables' O(1) exact lookup for prefix-query power a hash table structurally cannot offer.
Mental model
A trie is a tree where each edge is labeled with one character, and a path from the root spells out a string — every node along a stored word's path is shared with every other word starting the same way, so a prefix search is just walking down to that point in the tree once, not scanning every stored string.
Requires
- TreesComputer Science Fundamentals
A trie is a specialized tree where structure encodes string prefixes directly in the path from root to node; you need general tree traversal already understood before this specialization's insert/search operations make sense.
- Strings & TextProgramming Fundamentals
A trie is built entirely around character-by-character string decomposition; you need string/character indexing fluency for the trie's edge-per-character structure to be legible.
Used in
- Autocomplete and typeahead search suggestions
- Spell checkers, testing whether a word or valid prefix exists
- IP routing tables, using a trie over binary address prefixes
- Word games and dictionary-based validation (e.g. Boggle solvers)
Projects
- Implement a trie supporting insert, exact search, and prefix search (startsWith) from scratch
- Build an autocomplete feature backed by a trie that returns all stored words matching a given prefix
Examples
- Searching for all words starting with 'pre' in a trie is a single walk down 3 edges, then a traversal of everything below that node — no scanning of unrelated words
- cat and car share the same first two trie nodes (c, a), diverging only at the third character — the shared prefix is stored exactly once
Resources
- Tries — MIT 6.006course
Mastery checklist
- I can implement a trie with insert, exact search, and prefix search
- I can explain why a trie answers prefix queries a hash table structurally cannot
- I can implement a basic autocomplete feature using a trie
- I can explain the space/time tradeoff a trie makes compared to storing strings in a hash set