Topic 15 / 16
Tries
HardNon-Linear~4 days
Challenging
progress0 / 10 solved
Prefix tree for O(m) string search. Essential for autocomplete, spell-check, and word problems.
Prerequisites
Concept
A Trie (prefix tree) is a tree where each node represents one character of a string. Every path from root to a leaf encodes a complete word. Insert and search are both O(m) where m = word length — independent of how many words are stored. This beats HashMap for prefix queries because a Trie groups words by shared prefixes naturally.
When to use this pattern
- ◆Autocomplete — find all words with a given prefix
- ◆Word search / word dictionary problems
- ◆Longest common prefix across a set of strings
- ◆Replace words with their root (prefix replacement)
- ◆Any problem where prefix matching is a core operation
Common patterns
TrieNode class
Each node has children[26] (or a Map) and an isEnd flag.
Insert
Walk character by character, create nodes as needed, mark isEnd at last char.
Search
Walk character by character; return false if any node is missing.
StartsWith (prefix search)
Same as search but don't require isEnd at the end.
DFS on Trie
Collect all words under a prefix node by DFS traversal.
Brute force → optimal thinking
Brute force
Store all words in a list. For prefix search, iterate all words and check startsWith() → O(n × m) per query.
Observation
Words with the same prefix share a path. We only need to traverse that prefix once, then branch.
Optimization
Build a Trie. Insert in O(m). Any prefix query traverses at most m nodes — completely independent of dictionary size.
Final complexity
O(m) insert and search where m = word length. O(n × m) space for n words of average length m.
Quick Recall Check
What is the time complexity of searching for a word of length m in a Trie?
When does a Trie outperform a HashMap for string problems?
In a Trie node, what marks the end of a valid word?
Am I ready to move on?
Check each question you can answer confidently before moving to the next topic.
Progress is saved on this device