Trie Structure
root
/ \
a b
| |
p a
/ \ |
p e* d*
|
l
|
e*
Words: "apple" (a→p→p→l→e*), "ape" (a→p→e*), "bad" (b→a→d*). * marks word end.
Insert: O(L) — create nodes for each char
Search: O(L) — follow char path
Prefix: O(L) — same as search, no isEnd check
Standard Trie Implementation
C++
struct TrieNode {
TrieNode* children[26] = {};
bool isEnd = false;
};
class Trie {
TrieNode* root = new TrieNode();
public:
void insert(string word) {
TrieNode* cur = root;
for(char c : word) {
int i = c-'a';
if(!cur->children[i]) cur->children[i] = new TrieNode();
cur = cur->children[i];
}
cur->isEnd = true;
}
bool search(string word) {
TrieNode* cur = root;
for(char c : word) {
int i = c-'a';
if(!cur->children[i]) return false;
cur = cur->children[i];
}
return cur->isEnd;
}
bool startsWith(string prefix) {
TrieNode* cur = root;
for(char c : prefix) {
int i = c-'a';
if(!cur->children[i]) return false;
cur = cur->children[i];
}
return true;
}
};
// Insert/Search/StartsWith: O(L) time, O(L) space per insert
Interactive: Trie Search
Search for "ape" in a trie containing "apple" and "ape". Each cell is one character in the query — traverse the trie char by char, O(L) total regardless of dictionary size.
Practice Problems
#208Implement Trie (Prefix Tree)Medium
Implement a trie with insert, search, and startsWith operations.
Pattern: Use the standard Trie implementation shown above. Each node has 26 children pointers.
C++
// Use the Trie class defined above — it IS the solution
// Time per op: O(L) Space: O(total_chars)
#211Design Add and Search Words Data StructureMedium
Like Trie, but search supports '.' as wildcard matching any letter.
Pattern: Modified Trie. When searching and char is '.', try all 26 children recursively.
C++
struct Node { Node* ch[26]={}; bool end=false; };
class WordDictionary {
Node* root=new Node();
bool dfs(Node* n, string& w, int i) {
if(i==w.size()) return n->end;
if(w[i]!='.') {
int c=w[i]-'a';
return n->ch[c] && dfs(n->ch[c],w,i+1);
}
for(int c=0;c<26;c++)
if(n->ch[c] && dfs(n->ch[c],w,i+1)) return true;
return false;
}
public:
void addWord(string w) {
Node* cur=root;
for(char c:w) { if(!cur->ch[c-'a']) cur->ch[c-'a']=new Node(); cur=cur->ch[c-'a']; }
cur->end=true;
}
bool search(string w) { return dfs(root,w,0); }
};
#421Maximum XOR of Two Numbers in an ArrayMedium
Find the maximum value of nums[i] XOR nums[j] over all pairs.
Pattern: Binary trie — children are bits 0/1 instead of letters. Insert every number MSB-first, then for each number walk the trie greedily taking the opposite bit whenever possible (opposite bits set 1s in the XOR from the top down).
C++
struct Node { Node* ch[2]={}; };
int findMaximumXOR(vector<int>& nums) {
Node* root=new Node();
for(int x:nums) { // insert, MSB first
Node* cur=root;
for(int b=30;b>=0;b--) {
int bit=(x>>b)&1;
if(!cur->ch[bit]) cur->ch[bit]=new Node();
cur=cur->ch[bit];
}
}
int best=0;
for(int x:nums) { // query: prefer opposite bit
Node* cur=root; int v=0;
for(int b=30;b>=0;b--) {
int want=((x>>b)&1)^1;
if(cur->ch[want]) { v|=(1<<b); cur=cur->ch[want]; }
else cur=cur->ch[want^1];
}
best=max(best,v);
}
return best;
}
// Time: O(n·31) Space: O(n·31)
#212Word Search IIHard
Find all words from a dictionary that exist in a 2D board. Can't reuse cells.
Pattern: Build Trie from words. DFS from each cell, follow Trie. When isEnd=true, found a word. Prune when no Trie path exists.
C++
struct Node { Node* ch[26]={}; string word; };
void dfs(vector<vector<char>>& b, Node* n, int r, int c, vector<string>& res) {
if(r<0||r>=b.size()||c<0||c>=b[0].size()||b[r][c]=='#') return;
int i=b[r][c]-'a';
if(!n->ch[i]) return;
n=n->ch[i];
if(!n->word.empty()) { res.push_back(n->word); n->word=""; }
char tmp=b[r][c]; b[r][c]='#';
dfs(b,n,r+1,c,res); dfs(b,n,r-1,c,res);
dfs(b,n,r,c+1,res); dfs(b,n,r,c-1,res);
b[r][c]=tmp;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
Node* root=new Node();
for(auto& w:words) {
Node* cur=root;
for(char c:w) { if(!cur->ch[c-'a']) cur->ch[c-'a']=new Node(); cur=cur->ch[c-'a']; }
cur->word=w;
}
vector<string> res;
for(int r=0;r<board.size();r++)
for(int c=0;c<board[0].size();c++)
dfs(board,root,r,c,res);
return res;
}
Trie vs HashMap: HashMap can do O(L) prefix check too, but Trie is better for: prefix enumeration, pattern matching with wildcards, XOR-based maximum (binary trie).
Deeper Understanding
🧠 Under the Hood — shared prefixes are stored once
A trie is a tree where the path spells the key — the node itself stores almost nothing. That's why prefix operations are free: all words starting with "ap" live in exactly one subtree, so autocomplete is "walk L nodes, then DFS the subtree". A hash set scatters related keys uniformly (by design!), destroying prefix locality — great for exact membership, useless for enumeration.
⚖️ When to Use / When NOT to Use
✅ Use when you need prefix queries: autocomplete, startsWith, "count words with prefix"
The prefix IS a node — everything below it matches, O(L) to find.
✅ Use when matching many patterns against text simultaneously (Word Search II)
One trie walk advances all dictionary words at once, and dead branches prune the DFS.
✅ Use when maximizing XOR — a binary trie over bits, MSB first
Greedy bit-by-bit choice needs "does a number with this bit-prefix exist?", exactly what a trie answers.
❌ Avoid when you only need exact membership or key→value lookup
Instead: unordered_set/map — same O(L), far less memory, better cache behavior.
🚫 Common Misconceptions
"Tries save memory because prefixes are shared"
Usually the opposite: every node carries 26 pointers (208 bytes each on 64-bit). Sharing helps only with heavily overlapping keys. For memory, use `array[26]` → `unordered_map<char,Node*>` or a compressed (radix) trie.
"Search hitting a node means the word exists"
Reaching 'e' in "ape" only proves the prefix exists — the isEnd flag is what distinguishes a stored word from a prefix of one. Forgetting it is the #1 trie bug.
"Trie operations are O(1) because depth is bounded"
They're O(L) in the key length — for long strings that's the same as hashing the string. The win is what happens after the walk (enumeration, wildcards), not the walk itself.
🎤 Interview Follow-ups
"array[26] children or unordered_map — trade-offs?"
Array: O(1) child access, cache-friendly, 26 pointers even for leaf-heavy tries. Map: memory proportional to actual children, slower constant, needed for Unicode alphabets. State the alphabet-size assumption first.
"How do you delete a word from a trie?"
Unset isEnd, then walk back up freeing nodes that have no children and no isEnd — easiest recursively, returning "can prune" up the call stack. Reference counting per node also works.
"Why insert MSB-first in the XOR trie?"
XOR maximization is greedy from the most significant bit — a 1 at bit 30 beats 1s at all lower bits combined (2³⁰ > 2³⁰−1). MSB-first ordering lets the trie walk make that greedy choice level by level.