Tries (Prefix Trees)
A tree keyed by characters for fast prefix queries — autocomplete, word dictionaries with wildcards, grid word search, and binary tries for XOR problems.
What a trie is
A trie stores strings character by character along root-to-node paths. Words sharing a prefix share the same path.
Words: cat, car, cart, dog
(root)
/ \
c d
| |
a o
/ \ |
t* r* g*
|
t* * = end of a word
| Operation | Trie | Hash set |
|---|---|---|
| insert / exact lookup | O(L) | O(L) average (hashing) |
| all words with prefix p | O(len(p) + output) | O(total size) scan |
| longest prefix of s that is a word | O(L) | O(L²) |
| wildcard / char-by-char search | natural DFS | awkward |
L = word length.
Implementation
class TrieNode:
__slots__ = ("children", "is_end")
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def _walk(self, s):
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def startsWith(self, prefix):
return self._walk(prefix) is not None
struct TrieNode {
TrieNode* ch[26] = {};
bool isEnd = false;
};
class Trie {
TrieNode* root = new TrieNode();
TrieNode* walk(const string& s) {
TrieNode* n = root;
for (char c : s) {
n = n->ch[c - 'a'];
if (!n) return nullptr;
}
return n;
}
public:
void insert(const string& w) {
TrieNode* n = root;
for (char c : w) {
if (!n->ch[c - 'a']) n->ch[c - 'a'] = new TrieNode();
n = n->ch[c - 'a'];
}
n->isEnd = true;
}
bool search(const string& w) { auto n = walk(w); return n && n->isEnd; }
bool startsWith(const string& p) { return walk(p) != nullptr; }
};
Extra fields you can store per node
count— how many words pass through (prefix counts, deletion support).word— the full word at its end node (saves rebuilding strings in DFS).top3— best suggestions for autocomplete.sum/value— aggregated values for Map Sum Pairs.
Wildcard search
def search_with_dots(root, word):
def dfs(node, i):
if i == len(word):
return node.is_end
ch = word[i]
if ch == ".":
return any(dfs(child, i + 1) for child in node.children.values())
child = node.children.get(ch)
return child is not None and dfs(child, i + 1)
return dfs(root, 0)
Grid search for many words (Word Search II)
Searching each word separately is too slow. Instead, DFS the grid while walking the trie: a path is abandoned as soon as it's not a prefix of any word.
def find_words(board, words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w # store the word at its end
R, C = len(board), len(board[0])
found = []
def dfs(r, c, parent):
ch = board[r][c]
node = parent[ch]
if "$" in node:
found.append(node.pop("$")) # pop → never report twice
board[r][c] = "#"
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
dfs(nr, nc, node)
board[r][c] = ch
if not node: # prune exhausted branches
parent.pop(ch)
for r in range(R):
for c in range(C):
if board[r][c] in root:
dfs(r, c, root)
return found
The pruning step (removing trie leaves once their words are found) is what makes this pass on large inputs.
Autocomplete / suggestions
Option A: store up to 3 lexicographically smallest words at each node during insertion (insert words in sorted order and append while len < 3).
Option B (often simpler): sort the words and binary search each prefix:
from bisect import bisect_left
def suggested_products(products, search_word):
products.sort()
res, prefix = [], ""
for ch in search_word:
prefix += ch
i = bisect_left(products, prefix)
res.append([p for p in products[i:i + 3] if p.startswith(prefix)])
return res
Binary trie for XOR problems
Treat each integer as a 31- or 32-bit string from the most significant bit. To maximize x ^ y, walk the trie choosing the opposite bit whenever possible — higher bits dominate lower ones, so greedy is optimal.
struct BinTrie {
vector<array<int, 2>> nxt{{0, 0}};
void insert(int x) {
int n = 0;
for (int b = 30; b >= 0; b--) {
int bit = x >> b & 1;
if (!nxt[n][bit]) { nxt[n][bit] = nxt.size(); nxt.push_back({0, 0}); }
n = nxt[n][bit];
}
}
int maxXor(int x) { // assumes at least one number inserted
int n = 0, res = 0;
for (int b = 30; b >= 0; b--) {
int want = (x >> b & 1) ^ 1;
if (nxt[n][want]) { res |= 1 << b; n = nxt[n][want]; }
else n = nxt[n][want ^ 1];
}
return res;
}
};
Variants: Maximum XOR With an Element From Array (sort queries offline by limit, insert numbers ≤ limit), subarray max XOR (insert prefix XORs).
Complexity
- Insert/search: O(L).
- Space: O(total characters × alphabet) worst case for array children; O(total characters) for map children.
Common mistakes
- Confusing
search(needsis_end) withstartsWith. - Rebuilding strings at every DFS step (O(L²)); store the word at the end node or pass a list and join once.
- Reporting duplicate words in grid search (clear the end marker after finding).
- Memory blow-up with
[26]arrays for millions of nodes — use maps or a flat pool.
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.