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.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a trie and when should you use it over a hash set?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A trie (prefix tree) stores strings character by character. Each node represents a character; paths from root to marked nodes form complete words. Use a trie over a hash set when: (1) You need prefix queries – "find all words starting with prefix p" is O(len(p) + results) with a trie but requires scanning all keys with a hash set. (2) You need to find the longest matching prefix (autocomplete, replace words). (3) The problem involves a structured space of strings sharing common prefixes. Use a hash set when you only need exact membership lookup with no prefix queries – it is simpler and has O(1) average lookup. Memory: trie uses more memory than a hash set for sparse key sets, less for dense key sets with long common prefixes.”}},{“@type”:”Question”,”name”:”How do you implement Word Search II (LC 212) efficiently with a trie?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Build a trie from all words. DFS on each cell of the board. At each step, check if the current character exists in the trie node (prune if not). When a word endpoint is reached, add to results and set the trie node word to None to avoid duplicates. Critical optimization: after finding a word, prune dead trie branches – if a trie node has no children and no word, remove it from its parent. This prevents re-exploring paths for already-found words. Without pruning, the algorithm revisits the same trie paths many times. Time complexity: O(M * 4 * 3^(L-1)) where M is board cells and L is max word length.”}},{“@type”:”Question”,”name”:”How does a bitwise trie work for XOR maximum?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A bitwise trie stores integers bit by bit from the most significant bit (bit 31 or 30) to least significant. Each node has two children: 0 and 1. To find the maximum XOR of a number with any number in the trie: traverse from MSB to LSB, at each level try to go the opposite direction of the current bit (to maximize XOR). If the opposite direction exists, go there and set that XOR bit to 1. Otherwise, go the same direction (XOR bit = 0). This runs in O(32) = O(1) per query after O(n * 32) build. LC 421 (Maximum XOR of Two Numbers), LC 1707 (Maximum XOR with an Element from Array).”}},{“@type”:”Question”,”name”:”How do you implement autocomplete with a trie?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Augment each trie node with a frequency count (how many times the word was searched). On insertion, increment the frequency at the terminal node. For autocomplete: traverse the trie to the end of the prefix (O(len(prefix))). Then DFS from that node to collect all words, using a max-heap of size k to track the top-k by frequency. Optimization: store the top-3 results at each node during insertion, updated with each new insertion. This reduces autocomplete queries to O(len(prefix)) with O(words * len(word)) preprocessing space. For real-time autocomplete at scale, add a Redis sorted set per popular prefix as an L1 cache in front of the trie.”}},{“@type”:”Question”,”name”:”What is the time and space complexity of a trie?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Insert: O(L) where L is the word length. Search: O(L). Starts-with prefix check: O(L). Space: O(ALPHABET_SIZE * N * L) worst case – each node has up to ALPHABET_SIZE (26 for lowercase) children pointers, N words, average length L. In practice much less if words share prefixes. Optimization: use a hash map for children instead of a fixed array – reduces space from O(26 * N * L) to O(N * L) but adds hash map overhead. For problems with only lowercase letters, a 26-length array is typically fast enough. For Unicode or large alphabets, always use a hash map.”}}]}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.