Pattern 16 · Strings & Trees
Trie
A prefix tree (pronounced "try"): one character per node, so words that share a prefix share a path from the root. The structure behind autocomplete, multi-word grid search, and wildcard matching — everything a hash set can't do, in O(m) per operation.
insert / search O(m)space O(n · m)variants dict · binary triepractice 9 problems
01 core concept
Words that share a prefix share a path
Each node holds a children map (char → node) and an is_end flag.
Inserting a word means walking down from the root one character at a time,
creating nodes only where the path doesn't exist yet, then flagging the
final node as a complete word. The tree below is what
["apple", "app", "apt", "bat"] builds:
(root)
/ \
[a] [b]
| |
[p] [a]
/ \ |
[p]★ [t]★ [t]★
|
[l]
|
[e]★
★ = is_end (marks a complete word)
"apple", "app", "apt" share the "ap" path — stored once.
step 1 / 9walkthrough — insert "apple", "app", "apt"
trie nodes 0
words 0
Start with an empty trie — just a root. Insert apple: walk down from the root one character at a time. The cells show the characters of the word being inserted.
02 key properties
Everything is O(m)
With n = number of words and m = word length, no operation ever depends on n — only on the length of the word you're processing:
| operation | time | notes |
|---|---|---|
| Insert | O(m) | m = length of the word |
| Search | O(m) | Exact word lookup (checks is_end) |
| Prefix search | O(m) | Does any word start with this prefix? |
| Delete | O(m) | Remove the word, prune dead branches |
| Space | O(n · m) | Worst case; shared prefixes save space |
vsTrie or hash set?
| hash set | trie |
|---|---|
| O(1) exact lookup | O(m) exact lookup |
| No prefix search | O(m) prefix search |
| Each word stored separately | Shared prefixes stored once |
| No ordering | Lexicographic ordering built in |
03 recognition
When to reach for it
- You need to search by prefix, not just exact match.
- Autocomplete / suggestion systems.
- Searching multiple words at once in a grid or text — build the trie from the target words, walk the source once.
- Wildcard
'.'matching (trie + DFS). - Longest common prefix across many strings.
- XOR maximization problems → a binary trie over the bits.
When NOT to use it
If all you need is exact lookups, a hash set is simpler and O(1) —
skip the trie. Reach for a trie only when prefixes, wildcards, ordering,
or many-words-at-once matching are part of the problem.
04 implementation
The 25-line template — LC 208
Memorize this. Every trie problem starts from it, and insert,
search, and startsWith are the same walk with different endings.
trie.py — LC 208python
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # marks the end of a complete word
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, prefix: str) -> TrieNode:
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return nodestep 1 / 8walkthrough — three lookups in {apple, app, apt}
query search("ap")
The trie holds apple, app, apt. Three lookups, one walk: follow
children per character — the difference is only what you check at the end.search vs. startsWith
Both call the same _find walk. startsWith only asks
"does the path exist?" — search additionally requires
is_end on the final node. Forgetting that flag is Mistake 1 below.
05 problem patterns
Five shapes the trie takes
P1Trie + grid DFS — Word Search II (LC 212)
The classic "find multiple words in a grid" problem. Without a trie you'd DFS once per word; with a trie built from the target words you DFS the grid once and match all words simultaneously.
word_search_ii.py — LC 212python
def findWords(board, words):
# Build a trie from all target words
root = TrieNode()
for word in words:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = word # store the full word at the leaf
rows, cols = len(board), len(board[0])
result = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node.children:
return
next_node = node.children[ch]
if next_node.word: # found a complete word
result.append(next_node.word)
next_node.word = None # avoid duplicates
board[r][c] = '#' # mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, next_node)
board[r][c] = ch # restore
# PRUNING: remove leaf nodes with no children
if not next_node.children:
del node.children[ch]
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return resultGrid: o a t h Words: ["oath", "oat"]
e t a i Trie: (root) → o → a → t★ → h★
DFS from (0,0)='o':
→ (0,1)='a' matches the trie path
→ (0,2)='t' matches, t.word = "oat" FOUND
→ (0,3)='h' matches, h.word = "oath" FOUND
h has no children → prune 'h' from the trie
t has no children → prune 't' from the trie
…the trie is now empty — the DFS stops early.
P2Wildcard matching — Add & Search Words (LC 211)
word_dictionary.py — LC 211python
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
def dfs(idx, node):
for i in range(idx, len(word)):
ch = word[i]
if ch == '.':
# '.' matches any character - try all children
return any(dfs(i + 1, child)
for child in node.children.values())
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
return dfs(0, self.root)Trie of ["bat", "bit", "bot"]: Search "b.t":
(root) 'b' → match [b]
| '.' → try ALL children: [a], [i], [o]
[b] [a] → 't' → [t]★ is_end → FOUND
/ | \
[a] [i] [o]
| | |
[t]★ [t]★ [t]★
P3Shortest prefix — Replace Words (LC 648)
replace_words.py — LC 648python
def replaceWords(dictionary, sentence):
# Build a trie from the dictionary roots
root = TrieNode()
for word in dictionary:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def find_root(word):
node = root
for i, ch in enumerate(word):
if ch not in node.children:
return word # no prefix found
node = node.children[ch]
if node.is_end:
return word[:i + 1] # shortest prefix
return word
return ' '.join(find_root(w) for w in sentence.split())P4Autocomplete — Search Suggestions System (LC 1268)
search_suggestions.py — LC 1268python
def suggestedProducts(products, searchWord):
root = TrieNode()
for product in products:
node = root
for ch in product:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
node.word = product
def collect_words(node, results):
"""DFS to collect words in lexicographic order."""
if len(results) == 3:
return
if node.is_end:
results.append(node.word)
for ch in sorted(node.children): # sorted for lex order
collect_words(node.children[ch], results)
result = []
node = root
prefix_broken = False
for ch in searchWord:
if prefix_broken or ch not in node.children:
prefix_broken = True
result.append([])
else:
node = node.children[ch]
words = []
collect_words(node, words)
result.append(words)
return resultP5Binary trie — Maximum XOR (LC 421)
Store each number as a 32-step path of bits (MSB first). To maximize XOR against a number, greedily walk the trie taking the opposite bit whenever it exists.
max_xor.py — LC 421python
def findMaximumXOR(nums):
# Build a binary trie of all numbers (32-bit)
root = {}
for num in nums:
node = root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if bit not in node:
node[bit] = {}
node = node[bit]
max_xor = 0
for num in nums:
node = root
cur_xor = 0
for i in range(31, -1, -1):
bit = (num >> i) & 1
toggled = 1 - bit # we WANT the opposite bit
if toggled in node:
cur_xor |= (1 << i)
node = node[toggled]
else:
node = node[bit]
max_xor = max(max_xor, cur_xor)
return max_xor| problem | time | space |
|---|---|---|
| Implement Trie (208) | O(m) per op | O(n · m) |
| Word Search II (212) | O(R·C · 4^L) | O(n · m) |
| Add & Search Words (211) | O(26^m) worst | O(n · m) |
| Replace Words (648) | O(n · m) | O(d · k) |
| Search Suggestions (1268) | O(n·m + s·3) | O(n · m) |
| Maximum XOR (421) | O(n · 32) | O(n · 32) |
06 common mistakes
Where tries go wrong
Mistake 1 — forgetting the is_end check
Without it, search("app") returns True even when only "apple" was
inserted — the path exists, but no word ends there. search = path
exists and is_end; startsWith = path exists.
Mistake 2 — not pruning in Word Search II
Deleting exhausted leaf nodes (del node.children[ch]) shrinks the trie
as words are found. Skip it and large inputs TLE.
Mistake 3 — list[26] vs. dict for children
In Python a dict is cleaner (and handles any alphabet); the fixed
list[26] layout is the faster idiom in C++/Java. Don't cargo-cult the
array version into Python.
Mistake 4 — wildcard DFS on sliced strings
Recurse with an index (dfs(i + 1, child)), not a sliced string —
slicing copies O(m) characters at every level of the recursion.
Mistake 5 — not storing the full word at the leaf
In Word Search II, store node.word = word when building the trie.
Otherwise you must reconstruct the word from the DFS path — easy to get wrong
under pressure.
10 practice
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.
9 problems