Trie (Prefix Tree) Pattern
Tree where each edge is a character; O(L) insert/search/prefix.
When to Use It
Autocomplete, word search, longest common prefix, replace words, design search system.
Classic example: Implement Trie (insert, search, startsWith).
How It Works
A trie is a tree where each edge is a character and each path from root spells a string. Lookup, insert, and prefix-match all run in O(L) where L is the key length, independent of the number of stored keys. Compared to a hash set, you trade some memory (one node per character per branch) for O(L) prefix queries that hash sets can't do at all.
The 'isEnd' flag on a node marks where a complete word ends, distinguishing it from a mere intermediate prefix. This matters for problems like 'word break' where you need to know which prefixes are actual dictionary words.
Tries shine for autocomplete, longest-common-prefix, word search on grids (with backtracking), and any problem where many strings share prefixes. They also enable space-efficient implementations of 'replace words' and 'design search autocomplete system'. The trickiest use is XOR-maximization (max XOR of two numbers), where each number is stored as its bit-trie path and queries greedily descend toward the opposite bit at each level.
Key Insight
Trie operations are O(L) where L is the key length, completely independent of the dictionary size, making prefix queries (which hash sets can't answer at all) essentially free.
Templates
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean end;
}
class Trie {
TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.children[i] == null) node.children[i] = new TrieNode();
node = node.children[i];
}
node.end = true;
}
public boolean search(String word) {
TrieNode node = find(word);
return node != null && node.end;
}
public boolean startsWith(String prefix) {
return find(prefix) != null;
}
private TrieNode find(String s) {
TrieNode node = root;
for (char c : s.toCharArray()) {
node = node.children[c - 'a'];
if (node == null) return null;
}
return node;
}
}class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.end = True
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.end
def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, s: str):
node = self.root
for c in s:
if c not in node.children:
return None
node = node.children[c]
return nodeCommon Pitfalls
- Forgetting the isEnd flag and conflating 'a path exists' with 'a complete word exists'.
- Allocating a 26-slot array per node when the alphabet is sparse, wasting memory; a hash map of children is better for Unicode or sparse alphabets.
- In word-search-II, not pruning the trie as words are found, causing redundant exploration.
- Not sharing the trie between queries when the same dictionary is reused, paying O(sum of word lengths) per query unnecessarily.
- For 'remove word' / delete operations, forgetting to garbage-collect dead branches (or alternatively, just clearing isEnd and leaving the structure).
Variations
- Standard trie: insert, search, startsWith.
- Word search II on a grid: trie + depth-first search (DFS) with pruning.
- Replace words / longest-prefix replacement: search for shortest matching prefix.
- Bit trie for max XOR pair: greedy descent toward opposite bit per level.
- Compressed trie / radix tree: collapse single-child chains for memory.
Big O
- Time
- O(L) per insert/search/prefix
- Space
- O(total characters)