Tries¶
Also known as: Prefix Tree, Retrieval Tree
A tree where each edge is a character, so every path from the root spells a prefix. Looking up a word costs only its own length — completely independent of how many words you've stored.
Before you start¶
What 'solved properly' looks like
Target: O(L) per insert/search, where L is the word's length. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You build a tree where the root is empty and each node has up to 26 children (one per letter). To insert a word, you walk character by character, creating nodes that don't exist. To search, you walk the same path and check whether the final node is marked as the end of a word. The beauty is that lookup time depends only on the word's length, not on the number of words stored — a dictionary of a million words is as fast as a dictionary of ten.
Why it matters: Tries power autocomplete, spellcheck, IP routing, and any application that needs prefix-based search at scale. Combined with backtracking (Word Search II), it's also a genuine capstone problem that ties together multiple patterns from this roadmap.
When to reach for it¶
Reach for it when you need prefix search, autocomplete, "starts with", a dictionary of many words, or searching a board for many words at once (trie + backtracking).
When not to use it
Memory-hungry — a node per character per branch adds up fast. If you only ever need exact-match lookups, a hash set is simpler and smaller; the trie only earns its keep when you need prefix queries or you're matching many words against one structure at once.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Implement Trie (Prefix Tree) | LeetCode | Medium | 20 mins | teaching |
| 2 | Design Add and Search Words Data Structure | LeetCode | Medium | 25 mins | consolidation |
| 3 | Word Search II | LeetCode | Hard | 40 mins | challenge |
Already know this? Test out.
If you can solve Word Search II cleanly in one sitting — combining a trie with backtracking to search the board efficiently — you already own this pattern, so move on to the next one. Note this one is Hard and ties together multiple patterns; that's the point. If it doesn't come easily, work the set from the top.