All patterns
Prefix Trees (Trie)
Trees
Intermediate
Interactive
Follow one character edge per prefix symbol.
Time
O(p) prefix lookup
Space
O(total characters)
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.
The idea
A trie shares prefixes among words. Searching a prefix advances through one child per character; if an edge is missing, no stored word can begin with that prefix.
Analogy
A reusable way to think about organizing and navigating structured data efficiently.
When to reach for it
- The relationships between values drive the algorithm.
- You need efficient traversal, lookup, or updates.
- An interview problem names or implies this structure.
Language-independent template
node = root
for char in prefix:
if char not in node.children: return false
node = node.children[char]
return trueComplexity — time O(p) prefix lookup, space O(total characters).
Common mistakes
- Losing a pointer before saving its next target.
- Breaking the structure invariant during an update.
- Forgetting empty and single-node cases.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Easy
Index Pairs of a StringLC 1065
Find every text interval matching a dictionary word.
Medium
Support insert, exact search, and prefix search.
Hard
Word Search IILC 212
Find all dictionary words that can be formed in a board.
Variations
Traversal
Insertion and deletion
Search and reconstruction