Trie (Prefix Tree)
Tree where each edge is a character; O(L) insert/search/prefix.
Autocomplete, word search, longest common prefix, replace words, design search system.
Each operation walks at most L nodes, one per character of the word/prefix, independent of how many other words are stored. Space scales with the sum of all inserted word lengths.
The same idea applied in production systems — read these once you know the pattern to see where it lands in the real world.
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.
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.
- 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).
- Standard trie: insert, search, startsWith.
- Word search II on a grid: trie + 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.
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;
}
}Problems using this pattern
2Easiest first · Blind 75 above NeetCode 150