12. Tries
📋 Jump to TakeawaysA trie (pronounced "try") is a tree where each path from root to node represents a prefix. Instead of storing complete keys in each node like a BST, a trie stores one character per edge. This makes prefix operations — "find all words starting with 'pre'" — trivially fast.
The Structure
Each node has a dict of children and a boolean marking whether a word ends here.
# root
# |
# c
# |
# a
# / \
# t r
# (✓) (✓)
#
# "ca" is a prefix of both. "cat" and "car" are complete words.Implementation with TrieNode
LeetCode 208 - Implement Trie (Prefix Tree)
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
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.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def startsWith(self, prefix: str) -> bool:
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return TrueEvery operation is O(m) where m is the length of the word/prefix. Independent of how many words are stored.
Why dicts for children? A fixed-size array (like [None] * 26 in Go/Java) is faster but inflexible. Python dicts handle any character set — Unicode, digits, special characters — without wasting memory on unused slots. For interview problems, dicts are idiomatic Python.
Alternative: Nested Dict (No Class)
For quick prototyping, use nested dicts without defining a class:
from collections import defaultdict
def make_trie():
return defaultdict(make_trie)
trie = make_trie()
# Insert "cat"
trie['c']['a']['t']['$end'] = True
# Check "cat" exists
trie['c']['a']['t'].get('$end', False) # TrueThis is concise but harder to add methods to. The TrieNode class approach is better for interviews.
Delete Operation
Deleting from a trie requires removing nodes that are no longer part of any word:
class Trie:
# ... (insert, search, startsWith from above)
def delete(self, word: str) -> None:
self._delete(self.root, word, 0)
def _delete(self, node: TrieNode, word: str, depth: int) -> bool:
if depth == len(word):
if not node.is_end:
return False # word doesn't exist
node.is_end = False
return len(node.children) == 0 # delete node if no children
ch = word[depth]
if ch not in node.children:
return False
should_delete = self._delete(node.children[ch], word, depth + 1)
if should_delete:
del node.children[ch]
return not node.is_end and len(node.children) == 0
return FalseOnly remove a node if it has no children AND isn't the end of another word. "car" and "card" share the path c→a→r — deleting "car" clears is_end on 'r' but keeps the node because 'd' still needs it.
Wildcard Matching
The '.' wildcard matches any single character. Instead of following one path, try all children at that position.
LeetCode 211 - Design Add and Search Words Data Structure
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(node: TrieNode, i: int) -> bool:
if i == len(word):
return node.is_end
if word[i] == '.':
return any(dfs(node.children[ch], i + 1) for ch in node.children)
if word[i] not in node.children:
return False
return dfs(node.children[word[i]], i + 1)
return dfs(self.root, 0)This is what makes tries powerful for pattern matching — a dict can't do "find all words matching c.t" without checking every key.
Pattern: Autocomplete
Find all words with a given prefix. Navigate to the prefix node, then DFS to collect all words below it.
class Trie:
# ... (insert, search, startsWith from above)
def autocomplete(self, prefix: str) -> list[str]:
node = self.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
# DFS from this node to find all complete words
results: list[str] = []
def dfs(n: TrieNode, path: str) -> None:
if n.is_end:
results.append(path)
for ch in n.children:
dfs(n.children[ch], path + ch)
dfs(node, prefix)
return resultsThis is what powers search bars, IDE completions, and command-line tab completion.
Pattern: Word Search II (Trie + Backtracking)
Use a trie to efficiently check multiple words during grid backtracking:
LeetCode 212 - Word Search II
def findWords(board: list[list[str]], words: list[str]) -> list[str]:
# Build trie from 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 full word at end node
rows, cols = len(board), len(board[0])
result: list[str] = []
def dfs(r: int, c: int, node: TrieNode) -> None:
ch = board[r][c]
if ch not in node.children:
return
next_node = node.children[ch]
if hasattr(next_node, 'word') and next_node.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
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return resultWithout a trie, you'd search each word independently — O(words × cells × 4^L). The trie searches all words simultaneously by sharing prefix paths.
Trie vs Dict vs BST
| Operation | Trie | Dict | BST |
|---|---|---|---|
| Exact lookup | O(m) | O(m)* | O(m log n) |
| Prefix search | O(m) | O(n)** | O(m log n) |
| Autocomplete | O(m + k) | O(n) | O(m log n + k) |
| Sorted iteration | O(total chars) | O(n log n) | O(n) |
| Space | High | Medium | Medium |
*Hash computation is O(m). **Must check every key. k = number of results.
Tries win decisively for prefix operations. They lose on memory — each node is a dict with overhead per character.
Real-World Uses
Autocomplete — search engines, IDEs, command lines. Type a prefix, get suggestions instantly.
Spell checkers — check if a word exists, suggest corrections by exploring nearby paths.
IP routing — longest prefix match on binary tries. Router looks up "192.168.1.5" by walking the trie bit by bit.
DNS resolution — domain names are hierarchical strings, naturally trie-shaped.
T9 predictive text — old phone keyboards mapped digits to letters, tries found valid words.
When to Use Tries
- Prefix matching and autocomplete
- Dictionary lookups where prefix queries matter
- IP routing / longest prefix match
- Word search in grids (Boggle-style problems)
- When you have many strings sharing common prefixes
When NOT to Use Tries
- Just need exact key lookup → dict (simpler, less memory)
- Small dictionary → sorted list +
bisect - Keys aren't strings (integers, objects) → dict or BST
- Memory is tight — Python dicts per node have significant overhead
Practice Problems
| Problem | Difficulty | Link |
|---|---|---|
| Implement Trie (Prefix Tree) | Medium | LeetCode 208 |
| Design Add and Search Words Data Structure | Medium | LeetCode 211 |
| Word Search II | Hard | LeetCode 212 |
| Replace Words | Medium | LeetCode 648 |
| Map Sum Pairs | Medium | LeetCode 677 |
Key Takeaways
- A trie stores one character per edge — paths from root represent prefixes
- Python implementation uses nested dicts — flexible, handles any character set
- Insert, search, and prefix check are all O(m) where m is the key length
- Use
is_endboolean on each node to mark end-of-word - Tries are the only structure that makes prefix queries efficient — dicts can't do it
- Autocomplete is the killer app: navigate to prefix node, DFS to collect completions
- Dict-based tries have higher memory overhead per node than array-based tries, but are idiomatic Python
- Real-world uses: search autocomplete, spell check, IP routing, DNS