Trie (pattern)
Grokking arc: The motivating problem is repeated prefix checking against many words or many bit strings. Brute force scans every candidate. Can we do better? Share prefixes in a trie so each next character or bit decides whether a whole branch remains possible.
Why trie patterns exist — the story
A normal string search treats every word like a stranger. If your dictionary is cat, car, cart, and dog, and you ask whether the grid path c → a → r → ... can become a word, a brute-force checker may compare that prefix against every dictionary entry again and again. A trie changes the conversation: all words that start with ca share one hallway, so walking c, then a, answers "does any target still remain possible?" in O(1) per letter. The moment the hallway ends, you stop exploring.
That shared-prefix idea is why trie questions often pair with another technique. In Word Search II, the trie is the dictionary brain and backtracking is the board explorer. The DFS does not ask, "Is this complete path one of 30,000 words?" after every move. It asks, "Does this next letter exist from my current trie node?" If not, the entire branch dies immediately. For board paths like o → a → x, and a dictionary containing oath but no word beginning oax, the trie saves you from exploring every continuation under x.
The same idea works when the alphabet is not letters but bits. For maximum XOR, insert numbers as 32-bit paths. Query 5 (00101 in a tiny 5-bit story) against 3,10,25: at the highest bit, XOR wants the opposite bit because 1 beats 0 in that position. If the query bit is 0, prefer a stored 1; if the query bit is 1, prefer a stored 0. With 5 and 25 (11001), those opposite choices produce 11100 = 28. You did not compare 5 against every number one by one; the binary trie let you greedily choose the best available partner bit-by-bit in O(32).
The pattern chapter is about those applications. For the mechanics of a trie node, insert, search, and startsWith, see the Trie deep-dive in Part III.
A trie turns many repeated prefix checks into one shared walk. A binary trie does the same thing for bits: build once, then each query makes 32 greedy choices instead of scanning all prior numbers.
Recognize by
- prefix queries against a shared dictionary — "starts with," "autocomplete," "replace by root," "dictionary path"
- many target strings tested against the same search space — especially grid DFS plus a word list
- XOR-max wording — "maximum XOR pair," "best XOR under a limit," "count pairs with XOR in range"
- wildcard or streaming suffix checks — store words reversed when the query arrives from the end
- longest/shortest prefix match — routing tables, root replacement, command dictionaries
When NOT to use it
- The dictionary is tiny and the strings are short; a linear scan may be clearer and fast enough.
- You need arbitrary substring or suffix search without reversing/preprocessing; tries are prefix-first.
- You only perform one lookup; building the trie may cost more than the lookup it saves.
- Your alphabet is huge and sparse without many shared prefixes; a hash set of full strings may be simpler.
- You need sorted order of complete words more than prefix pruning; a sorted array plus binary search can be enough.
How to use it — binary-trie template for max-XOR
Use a binary trie when each element is a fixed-width bit string. Java int problems usually walk bits 31 down to 0; if values are guaranteed non-negative under 2^31, you can still keep 31 or 32 levels and the code stays simple.
class BitNode { BitNode[] child = new BitNode[2]; }
void insert(BitNode root, int x) {
BitNode cur = root;
for (int b = 31; b >= 0; b--) {
int bit = (x >>> b) & 1;
if (cur.child[bit] == null) cur.child[bit] = new BitNode();
cur = cur.child[bit];
}
}
int bestXorAgainst(BitNode root, int x) {
BitNode cur = root;
int ans = 0;
for (int b = 31; b >= 0; b--) {
int bit = (x >>> b) & 1;
int want = bit ^ 1;
if (cur.child[want] != null) {
ans |= 1 << b;
cur = cur.child[want];
} else {
cur = cur.child[bit];
}
}
return ans;
}once you decide a higher XOR bit can be 1, no later lower bit can compensate for losing it. That is why the MSB-first opposite-bit walk is safe.
When to use it — trie pattern flavors
| Flavor | Recognizer phrasing | What the trie contributes |
|---|---|---|
| Dictionary-pruned DFS | "find all words on a board", "many target strings" | kills paths as soon as their prefix is absent |
| Shortest/longest prefix | "replace by root", "routing prefix", "autocomplete" | walks one path and stops at the first or deepest useful terminal |
| Wildcard branching | "? / . can match any letter" | branches only at wildcard positions instead of scanning every word |
| Binary XOR trie | "maximum XOR", "XOR under limit", "count XOR pairs" | chooses opposite bits greedily from most significant to least |
| Streaming suffix query | "does the stream end with any word?" | store reversed words, then walk the recent stream backward |
The important interview move is to name the alphabet. Letter tries branch over characters. Binary tries branch over 0/1 bits. Reversed tries branch over the query from the end. Once you say that out loud, the code becomes a normal walk with a different interpretation of "next edge."
When NOT to use it
- You have very few short strings — a plain
HashSet<String>is faster and simpler. Tries pay for themselves at ~1000+ words or when you need prefix / wildcard / streaming semantics. - You need only whole-word membership, no prefix operations — hash sets win on memory (no per-character overhead) and CPU (one hash vs. one walk).
- Memory is critically tight — a trie node in Java holds 26 pointers just for lowercase letters (~200 bytes per node). A million-word dictionary can eat 1 GB. Alternatives: Ternary Search Trees (3 pointers per node), DAWG / DAFSA (merge equivalent suffixes), compressed trie (Patricia / Radix tree — collapse single-child chains).
- The alphabet is huge — Unicode with 1M+ code points makes 26-pointer arrays absurd. Use
HashMap<Character, Node>per node, or switch to a suffix automaton. - Queries are exact-match only — the exact-match
HashMapbeats trie walks on both memory and lookup time. - You need range queries or ordering — tries iterate in lexicographic order but don't support "words in range [aardvark, badger]" efficiently.
TreeMapis O(log n) and cleaner.
The templates
Template 1: Basic 26-way letter trie
class Trie {
Trie[] next = new Trie[26]; // one pointer per lowercase letter
boolean end = false; // marks end-of-word
void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.next[i] == null) node.next[i] = new Trie();
node = node.next[i];
}
node.end = true;
}
boolean search(String word) {
Trie node = walk(word);
return node != null && node.end;
}
boolean startsWith(String prefix) {
return walk(prefix) != null;
}
private Trie walk(String s) {
Trie node = this;
for (char c : s.toCharArray()) {
int i = c - 'a';
if (node.next[i] == null) return null;
node = node.next[i];
}
return node;
}
}Complexity: O(L) insert / search / startsWith, where L is word length. Space: O(alphabet × total characters) worst case.
Template 2: Binary trie (32-bit) for max-XOR
class BinaryTrie {
BinaryTrie[] next = new BinaryTrie[2];
void insert(int x) {
BinaryTrie node = this;
for (int b = 31; b >= 0; b--) {
int bit = (x >> b) & 1;
if (node.next[bit] == null) node.next[bit] = new BinaryTrie();
node = node.next[bit];
}
}
int maxXor(int q) { // best XOR partner for q
BinaryTrie node = this;
int result = 0;
for (int b = 31; b >= 0; b--) {
int bit = (q >> b) & 1;
int want = 1 - bit; // XOR wants the opposite bit
if (node.next[want] != null) {
result |= (1 << b);
node = node.next[want];
} else {
node = node.next[bit];
}
}
return result;
}
}Complexity: O(32) per operation. Independent of stored count. Key move: at every bit, prefer the opposite bit — greedy from MSB.
Template 3: Wildcard search (. matches any)
boolean searchWildcard(Trie node, String word, int i) {
if (i == word.length()) return node.end;
char c = word.charAt(i);
if (c == '.') {
for (Trie child : node.next)
if (child != null && searchWildcard(child, word, i + 1)) return true;
return false;
} else {
Trie child = node.next[c - 'a'];
return child != null && searchWildcard(child, word, i + 1);
}
}Complexity: O(26^k) worst case where k = number of wildcards. In practice, most . positions branch to very few children.
Complexity summary
| Operation | Time | Space | Notes |
|---|---|---|---|
| Insert word of length L | O(L) | O(alphabet × L) worst | Amortize across shared prefixes |
| Search / startsWith | O(L) | O(1) auxiliary | Constant-space walk |
| Delete | O(L) | O(1) | Optionally prune unused branches |
| All words with prefix P | O(L + total chars in matches) | O(1) | DFS from prefix's end node |
| Max XOR | O(32) | O(1) | Independent of stored count |
Traps & gotchas — the 5 that fail candidates on interview day
Without it, search("app") returns true even if only "apple" was inserted. Every terminal node needs an explicit "word ends here" boolean. Rule: insert sets end = true on the last node; search verifies end == true at the walk's end.
When you find "cat" on the board, if you don't remove it from the trie (set end = false) or from your result set, you'll emit it multiple times if it can be spelled multiple ways. Rule: after collecting a word, either remove its terminal or add to a Set<String> to dedupe.
Classic backtracking bug. Mark the cell before recursing; unmark after. Trie navigation and board navigation are independent — track both. Rule: board[r][c] = '#'; dfs(...); board[r][c] = original;.
A trie for 100K English words allocates ~50M pointer slots at 8 bytes each = 400 MB. If the interviewer says "memory-constrained," switch to HashMap<Character, Node> (only allocate pointers actually used) or a compressed trie. Rule: mention this trade-off explicitly when discussing memory.
For max-XOR, always insert MSB-first. Bit 31 gives the largest place value, so choosing the "opposite bit" at the MSB matters most. Rule: iterate for (int b = 31; b >= 0; b--) — top down.
History — de la Briandais 1959, Fredkin 1960, Google's first index
The trie data structure was invented by René de la Briandais in 1959 as a compact way to store dictionaries in punch-card memory. Edward Fredkin independently rediscovered and named it in 1960: "trie" from "retrieval" (Fredkin insisted it should be pronounced "tree," but nobody listened; the standard pronunciation is "try").
Google's first web search index (1996-1998) was a trie of URL prefixes — that's how it did startsWith queries so cheaply while other search engines lagged. The Judy Array (2000s) was Doug Baskins' cache-aware trie variant for the Cray-1 supercomputer. Modern applications:
- Autocomplete everywhere — from your terminal shell (
bashcompletion) to Google Search's dropdown. - IP routing tables — every packet routing table on the internet is a Patricia trie (compressed trie) on IP address bit prefixes. Cisco's ASIC hardware performs the walk in one clock cycle.
- Ethereum's state tree is a Merkle Patricia trie — cryptographically verifiable trie of account states.
- Bioinformatics — suffix tries (Aho-Corasick, 1975) find all occurrences of multiple patterns in DNA sequences.
When you mention "we could compress single-child chains with a Patricia trie" in an interview, you're citing a data structure Cisco routers use to move billions of packets per second.
Canonical problem walkthrough — Word Search II
Problem (↗ LeetCode): Given an m × n board of characters and a list of words, return all words in the list that can be constructed from letters of sequentially adjacent cells. A cell may not be used more than once in a single word.
Approach 1 — Word Search I per word
For each word, run the O(m·n · 4^L) DFS from every cell.
List<String> findWordsBrute(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
for (String w : words) {
boolean found = false;
for (int r = 0; r < board.length && !found; r++)
for (int c = 0; c < board[0].length && !found; c++)
if (dfs(board, r, c, w, 0)) { res.add(w); found = true; }
}
return res;
}
boolean dfs(char[][] b, int r, int c, String w, int i) {
if (i == w.length()) return true;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] != w.charAt(i)) return false;
char tmp = b[r][c]; b[r][c] = '#';
boolean ok = dfs(b,r+1,c,w,i+1) || dfs(b,r-1,c,w,i+1) || dfs(b,r,c+1,w,i+1) || dfs(b,r,c-1,w,i+1);
b[r][c] = tmp;
return ok;
}Complexity: O(k · m · n · 4^L) where k = number of words. For 10⁴ words on a 15×15 board, this TLEs immediately.
Approach 2 — Trie of dictionary + single board DFS
Build a trie of all words. From each board cell, DFS once, walking the trie in parallel. The trie prunes: if the current cell's letter doesn't extend the trie path, the entire branch dies immediately.
class Trie {
Trie[] next = new Trie[26];
String word = null; // stored at terminals for direct collection
}
List<String> findWords(char[][] board, String[] words) {
Trie root = new Trie();
for (String w : words) {
Trie node = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (node.next[i] == null) node.next[i] = new Trie();
node = node.next[i];
}
node.word = w;
}
List<String> res = new ArrayList<>();
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
dfs(board, r, c, root, res);
return res;
}
void dfs(char[][] b, int r, int c, Trie node, List<String> res) {
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length) return;
char ch = b[r][c];
if (ch == '#' || node.next[ch - 'a'] == null) return;
node = node.next[ch - 'a'];
if (node.word != null) { res.add(node.word); node.word = null; } // dedupe
b[r][c] = '#';
dfs(b, r+1, c, node, res);
dfs(b, r-1, c, node, res);
dfs(b, r, c+1, node, res);
dfs(b, r, c-1, node, res);
b[r][c] = ch;
}Complexity: O(m · n · 4^L) where L is longest word. Dictionary-size factor eliminated — the trie prunes.
Interview commentary:
- "Brute force is O(k · 4^L) — for 10⁴ words it TLEs."
- "Trie shares prefixes so one board DFS finds all words simultaneously. The trie prunes any branch not represented in the dictionary."
- "Store
wordat the terminal instead of a boolean — makes collection O(1). Set to null after collecting to avoid duplicates." - "Standard mark-unmark backtracking on the board; the trie navigation is separate."
Approach 3 — Trie + prune empty branches
Optimize by removing trie nodes after all words in that subtree are found. Ensures the trie shrinks as we work, so later cells have less to explore.
Marginal improvement — mentioned as a follow-up in interviews, rarely coded.
Complexity ladder
| Approach | Time | Space | When |
|---|---|---|---|
| DFS per word | O(k · m · n · 4^L) | O(L) | Reference / k ≤ 10 |
| Trie + single DFS | O(m · n · 4^L) | O(dictionary chars) | Interview default |
| Trie with pruning | Slightly better in practice | O(dictionary chars) | Contest / large k |
Word Search II (Trie + Backtracking) Hard
car).Problem
Given a grid of letters and a dictionary, return all dictionary words that can be traced through adjacent cells (up/down/left/right), never reusing a cell within one word.
Constraints: grid up to 12×12; up to 3·10⁴ words.
Example 1: grid with words ["oath","pea","eat","rain"] → the traceable ones (e.g. ["oath","eat"]).
Example 2: Board [["a"]], words ["a","b"] → ["a"].
Solution — brute force
The straightforward approach is: for every word, run the single-word Word Search DFS over the board. That is easy to explain but terrible at scale because common prefixes are re-explored for every word.
for each word in words:
for each cell in board:
run DFS trying to spell exactly this word
if found, add it and stop searching this wordIf there are W words, average length L, and R·C cells, the worst case is roughly O(W·R·C·4^L). The trie solution pays O(total characters) once, then shares all prefix work across the dictionary.
Baseline complexity: O(W·R·C·4^L) worst case and O(L) recursion space per word search.
Solution — optimized
The optimized solution keeps the original Java intact and explains the pattern that removes the brute-force bottleneck.
Pattern
Insert all words into a trie, then DFS the grid once, walking the trie in lockstep — pruning every branch that leaves the trie.
With many query words, testing each independently is wasteful. The trie lets one grid DFS test all words at once: you only continue into a cell if the current character exists as a trie edge. Mark found words at terminal nodes.
The DFS position in the grid and the node in the trie always spell the same string; leaving the trie means no word can be completed down this path.
Java (core)
List<String> findWords(char[][] board, String[] words) {
Node root = buildTrie(words);
List<String> res = new ArrayList<>();
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
dfs(board, r, c, root, res);
return res;
}
void dfs(char[][] b, int r, int c, Node node, List<String> res) {
if (r < 0 || c < 0 || r >= b.length || c >= b[0].length) return;
char ch = b[r][c];
if (ch == '#') return;
Node nxt = node.next[ch - 'a'];
if (nxt == null) return; // prune: prefix not in any word
if (nxt.word != null) { res.add(nxt.word); nxt.word = null; } // dedup found
b[r][c] = '#'; // mark visited
dfs(b, r+1, c, nxt, res); dfs(b, r-1, c, nxt, res);
dfs(b, r, c+1, nxt, res); dfs(b, r, c-1, nxt, res);
b[r][c] = ch; // restore
}words ["oath","pea","eat","rain"] on a letter grid. Start from o: the trie has child o, then a, then t, then h, so that path can reach the terminal word "oath". Start from a path like o → a → x: after oa, there is no x child, so the DFS returns immediately. You are not checking four words separately; one prefix walk prunes the whole dictionary.
Same pattern, new tweaks
| Variation | The one thing that changes | Time |
|---|---|---|
| - Word Search (single word) — tweak: plain grid DFS, no trie needed. | — | |
| Concatenated Words | a trie of all words + DFS to test whether a word is built from shorter ones | — |
| Stream of Characters | store words reversed in a trie and match the incoming stream from the back | — |
| Replace Words | stop at the shortest terminal prefix instead of collecting all terminals | — |
| Add and Search Word | wildcard . branches into all children at that depth | — |
Re-adding a word for every path that reaches it. Example: board has multiple paths spelling "cat" from the same trie leaf. Without clearing node.word after the first find (or using a Set<String> result), you emit "cat" multiple times.
"I would not search each word independently because the dictionary has up to 30,000 words and many share prefixes. I build a trie once, then do board DFS while carrying the current trie node. If the next board letter is not a trie child, no dictionary word can continue, so I prune that branch. When I hit a terminal node, I record the word and clear it to avoid duplicates."
"Drive a backtracking search with a trie to prune multiple targets simultaneously" is a hallmark staff-level combination of two structures.
Time Complexity
Time O(R·C·4^L) worst but trie-pruned in practice · Space O(total chars).
Worst-case O(R·C·4^L), but trie prefix pruning avoids repeating work for shared dictionary prefixes.
Space Complexity
O(totalChars) for the trie plus O(L) recursion stack; result output extra.
Learning notes
- Why
buildTrie(words)first? — it shares all dictionary prefixes before the board DFS begins. - Why carry
Node nodein DFS? — the grid path and trie path must advance together. - Why
nxt == nullreturns immediately? — no dictionary word has this prefix, so every continuation is impossible. - Why
nxt.word = nullafter adding? — it deduplicates a word found through multiple paths. - Why mark
b[r][c] = '#'and restore? — one path cannot reuse a cell, but sibling paths need the original board.
Maximum XOR of Two Numbers (Binary Trie) Medium
↗ LeetCode: Maximum XOR of Two Numbers in an Array
Problem
Given an array, find the maximum XOR obtainable from any two elements.
Constraints: 1 ≤ n ≤ 2·10⁵; values 0 … 2³¹−1; aim to beat O(n²).
Example 1: [3,10,5,25,2,8] → 28 (5 XOR 25).
Example 2: [0] → 0 because the only possible pair value with itself is zero.
Solution — brute force
The brute-force version checks every pair. It is a good correctness baseline and a terrible final answer for n = 2·10^5.
int findMaximumXORBrute(int[] nums) {
int best = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
best = Math.max(best, nums[i] ^ nums[j]);
}
}
return best;
}That is O(n²) time and O(1) space. The optimized version keeps the same "best partner" idea but finds the partner by walking a trie of bits, so each number costs only 32 decisions.
One subtle choice: many solutions insert all numbers first and then query all numbers, as below. You can also insert numbers one at a time and query only against previously inserted numbers to avoid pairing a value with itself. For maximum XOR of two numbers, pairing with itself gives XOR 0, so it never incorrectly beats a positive answer; the all-first version is simpler.
Baseline complexity: O(n²) time and O(1) space.
Solution — optimized
The optimized solution keeps the original Java intact and explains the pattern that removes the brute-force bottleneck.
Pattern
Insert numbers bit-by-bit (MSB→LSB) into a binary trie; for each number, greedily walk toward the opposite bit to maximize XOR.
To maximize XOR, at each bit prefer the branch with the complementary bit (they differ → contributes 1 at that position). A binary trie makes this greedy choice O(32) per query.
Java (sketch)
class BinTrie { BinTrie[] c = new BinTrie[2]; }
int findMaximumXOR(int[] nums) {
BinTrie root = new BinTrie();
for (int x : nums) { // insert
BinTrie n = root;
for (int b = 31; b >= 0; b--) {
int bit = (x >> b) & 1;
if (n.c[bit] == null) n.c[bit] = new BinTrie();
n = n.c[bit];
}
}
int best = 0;
for (int x : nums) { // query best partner
BinTrie n = root; int cur = 0;
for (int b = 31; b >= 0; b--) {
int bit = (x >> b) & 1, want = bit ^ 1;
if (n.c[want] != null) { cur |= (1 << b); n = n.c[want]; }
else n = n.c[bit];
}
best = Math.max(best, cur);
}
return best;
}Use 5-bit versions for readability: 5 = 00101, 25 = 11001. Querying 5, the trie first wants 1 at the 16s bit and can take 25's branch, so the XOR gets a high 1. It next wants 1 at the 8s bit and again follows 25. Later bits contribute as available. The final path gives 00101 XOR 11001 = 11100 = 28, better than any pair in [3,10,5,25,2,8].
Why MSB-first matters
XOR is a number, not just a count of different bits. A 1 in the 16s place beats any combination of lower bits. That is why the trie walk starts from bit 31 and commits greedily. If the opposite branch exists at a high bit, take it. Even if that later forces weaker low bits, the high bit already dominates.
For a tiny 4-bit example, compare possible XORs for query 0101. A partner beginning with 1... gives a leading XOR bit 1, producing at least 1000 (8). A partner beginning with 0... leaves that bit 0, so the best it can do is 0111 (7). No later choice can recover the lost high bit. This is the same logic as choosing the lexicographically larger binary string when maximizing a number.
Same pattern, new tweaks
| Variation | The one thing that changes | Time |
|---|---|---|
| Maximum XOR With an Element From Array | answer queries offline, sorting by the value bound and inserting numbers as they become allowed | O((n+q)·32) |
| Count Pairs With XOR in a Range | store subtree counts in the binary trie and count paths whose XOR is < limit, then subtract | O(n·32) |
| Maximum Genetic Difference Query | add/remove ancestors in a binary trie during tree DFS | O((n+q)·32) |
| Replace Words / IP routing | the same longest-prefix idea, but over characters or address bits instead of XOR greed | — |
Comparing bits in the wrong direction. Example: numbers [3,10,5,25] — XOR-max hunt greedily wants the opposite bit at each level from the query. Insert MSB-first; at each level, walk the child whose bit differs from the current bit (fall back if that branch doesn't exist).
"Brute force compares every pair, but XOR is decided from the highest bit downward. I insert every number into a binary trie and, for each query number, prefer the opposite bit at each level. If the opposite branch exists, that bit of the answer becomes 1; otherwise I take the same-bit branch. The width is constant at 32, so the total time is O(n)."
Binary tries also answer Maximum XOR With an Element From Array (offline with a value bound) and range-XOR counting (store subtree counts). It is the bitwise cousin of prefix-tree search: different alphabet, same shared-path idea.
Time Complexity
Time O(n·32) · Space O(n·32).
O(n·32), which is O(n) for fixed-width Java integers.
Space Complexity
O(n·32) trie nodes in the worst case.
Learning notes
- Why walk bits from 31 down to 0? — higher XOR bits dominate every combination of lower bits.
- Why
want = bit ^ 1? — XOR gets a 1 exactly when the two bits differ. - Why set
cur |= (1 << b)only whenwantexists? — that bit can be made 1 only if an opposite branch is available. - Why insert all numbers first? — each query can choose among every potential partner in the array.
- Why pairing with itself is harmless here? — self-XOR is 0, which cannot beat a positive maximum pair.