Trie (prefix tree) problems appear frequently in coding interviews. This guide covers the core patterns with Python implementations you can adapt to any trie problem.
Trie Node Structure and Basic Operations (LC 208)
Every trie implementation starts with a node class and the three core operations: insert, search, and startsWith.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
def startsWith(self, prefix: str) -> bool:
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return TrueTime: O(m) for all operations where m is the word length. Space: O(m * n) total for n words of average length m.
Word Dictionary with Wildcards (LC 211)
When ‘.’ can match any character, use DFS through the trie trying all children at wildcard positions.
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
return self._dfs(word, 0, self.root)
def _dfs(self, word: str, i: int, node: TrieNode) -> bool:
if i == len(word):
return node.is_end
ch = word[i]
if ch == '.':
# Try all children
for child in node.children.values():
if self._dfs(word, i + 1, child):
return True
return False
else:
if ch not in node.children:
return False
return self._dfs(word, i + 1, node.children[ch])Word Search II (LC 212) – DFS on Board with Trie Pruning
Build a trie from all words, then DFS from every board cell. The key optimization: remove matched words from the trie to avoid duplicate results and speed up subsequent searches.
class TrieNodeWS:
def __init__(self):
self.children = {}
self.word = None # store complete word at end node
class Solution:
def findWords(self, board, words):
root = TrieNodeWS()
for w in words:
node = root
for ch in w:
if ch not in node.children:
node.children[ch] = TrieNodeWS()
node = node.children[ch]
node.word = w
rows, cols = len(board), len(board[0])
results = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node.children:
return
next_node = node.children[ch]
if next_node.word:
results.append(next_node.word)
next_node.word = None # remove to avoid duplicates
board[r][c] = '#' # mark visited
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
dfs(nr, nc, next_node)
board[r][c] = ch # restore
# Prune: remove leaf nodes with no remaining words
if not next_node.children and not next_node.word:
del node.children[ch]
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return resultsThe pruning step (deleting empty leaf nodes) is what separates a solution that times out from one that passes. After finding a word, its trie path becomes dead weight – remove it.
Auto-Complete System Design
A production auto-complete system uses a trie augmented with frequency counts and top-k results cached at each node.
import heapq
class AutocompleteNode:
def __init__(self):
self.children = {}
self.freq = 0
# Cache top-3 (word, freq) pairs at this node
self.top_k = [] # min-heap by freq
class AutocompleteSystem:
def __init__(self, sentences, times):
self.root = AutocompleteNode()
self.current = [] # characters typed so far
for s, t in zip(sentences, times):
self._insert(s, t)
def _insert(self, sentence: str, freq: int):
node = self.root
for ch in sentence:
if ch not in node.children:
node.children[ch] = AutocompleteNode()
node = node.children[ch]
# Update top-k at each node along the path
self._update_topk(node, sentence, freq)
node.freq += freq
def _update_topk(self, node, sentence, freq):
# Keep a min-heap of size 3
for i, (f, s) in enumerate(node.top_k):
if s == sentence:
node.top_k[i] = (freq, sentence)
heapq.heapify(node.top_k)
return
if len(node.top_k) node.top_k[0][0]:
heapq.heapreplace(node.top_k, (freq, sentence))
def input(self, c: str):
if c == '#':
sentence = ''.join(self.current)
self._insert(sentence, 1)
self.current = []
return []
self.current.append(c)
node = self.root
for ch in self.current:
if ch not in node.children:
return []
node = node.children[ch]
return [s for f, s in sorted(node.top_k, reverse=True)]Design notes: For real systems, the top-k cache makes each prefix lookup O(1) instead of O(subtree size). Trade-off: inserts become slower because you update cached results at every prefix node. With billions of queries, precompute top-k offline and store in Redis.
Bitwise Trie for XOR Maximum (LC 421)
Insert numbers bit by bit from MSB (bit 31) to LSB (bit 0). To find the number that maximizes XOR with a query, greedily go to the opposite bit at each level.
class BitwiseTrieNode:
def __init__(self):
self.children = [None, None] # index 0 or 1
class Solution:
def findMaximumXOR(self, nums) -> int:
root = BitwiseTrieNode()
def insert(num):
node = root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if not node.children[bit]:
node.children[bit] = BitwiseTrieNode()
node = node.children[bit]
def query(num) -> int:
node = root
xor = 0
for i in range(31, -1, -1):
bit = (num >> i) & 1
want = 1 - bit # go opposite to maximize XOR
if node.children[want]:
xor |= (1 << i)
node = node.children[want]
else:
node = node.children[bit]
return xor
for n in nums:
insert(n)
return max(query(n) for n in nums)This runs in O(32n) = O(n) time. The bitwise trie has at most 32 * n nodes for 32-bit integers.
Replace Words with Root (LC 648)
Build a trie from all roots. For each word in the sentence, walk the trie – if you hit an end node before consuming the full word, replace with the root.
class Solution:
def replaceWords(self, dictionary, sentence: str) -> str:
root = TrieNode()
for word in dictionary:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def replace(word):
node = root
for i, ch in enumerate(word):
if ch not in node.children:
return word # no root found
node = node.children[ch]
if node.is_end:
return word[:i+1] # replace with root
return word
return ' '.join(replace(w) for w in sentence.split())Pattern Recognition: Trie vs Hash Set
Use a trie when the problem involves prefix queries. Use a hash set when you need exact membership checks.
| Signal in problem | Data structure |
|---|---|
| “starts with”, “prefix”, “autocomplete” | Trie |
| “common prefix”, “replace by shortest prefix” | Trie |
| “find all words matching pattern” | Trie + DFS |
| “exists in set”, “seen before” | Hash set |
| “maximize XOR” | Bitwise trie |
| No prefix queries needed | Hash set (simpler, faster) |
Key trie trade-offs: faster prefix queries than hash set, but higher memory usage (each character is a node). For small alphabets (26 letters) this is fine. For Unicode, use a hash map for children instead of a fixed array.
Meta coding interviews frequently test trie problems. See common patterns for Meta interview: trie and string search problems.
Apple coding rounds include trie and string prefix problems. See patterns for Apple interview: trie and autocomplete system design.
LinkedIn engineering interviews test trie and autocomplete patterns. See common questions for LinkedIn interview: trie and search problems.