Trie Data Structure Interview Patterns: Autocomplete, Word Search & Prefix Problems
A Trie (prefix tree) is the go-to data structure for string prefix operations. It enables O(m) insert, search, and prefix queries where m is the word length—far faster than a hash set for prefix matching. Tries appear in autocomplete, spell checkers, IP routing, and word game problems.
Trie Fundamentals
- Structure — each node represents one character; root is empty; paths from root to leaf spell words
- Children — each node has up to 26 children (a-z) or a hash map for arbitrary character sets
- End marker — a boolean
is_endflag marks complete words - Time — O(m) insert, search, prefix check (m = word length)
- Space — O(n·m) worst case, but shared prefixes save memory
Trie Implementation
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
self.count = 0 # words ending here (optional)
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 starts_with(self, prefix: str) -> bool:
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True
Pattern 1: Autocomplete / Search Suggestions
Build a Trie, then DFS from the prefix node to collect all words:
def autocomplete(trie, prefix):
node = trie.root
for ch in prefix:
if ch not in node.children:
return []
node = node.children[ch]
# DFS to collect all words with this prefix
results = []
def dfs(cur, path):
if cur.is_end:
results.append(prefix[:-len(path)] + path if path else prefix)
for ch, child in cur.children.items():
dfs(child, path + ch)
dfs(node, "")
return results
Pattern 2: Word Search with Wildcards
Implement search with ‘.’ wildcard that matches any character:
def search_with_wildcard(node, word, i):
if i == len(word):
return node.is_end
ch = word[i]
if ch == '.':
return any(search_with_wildcard(child, word, i+1)
for child in node.children.values())
if ch not in node.children:
return False
return search_with_wildcard(node.children[ch], word, i+1)
Pattern 3: Word Break Problem
Use Trie with DP to check if a string can be segmented into dictionary words:
def word_break(s, word_dict):
trie = Trie()
for w in word_dict:
trie.insert(w)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(n):
if not dp[i]:
continue
node = trie.root
for j in range(i, n):
ch = s[j]
if ch not in node.children:
break
node = node.children[ch]
if node.is_end and dp[i]:
dp[j+1] = True
return dp[n]
Pattern 4: Maximum XOR (Bitwise Trie)
Binary Trie where each bit is a node. Find pair with maximum XOR in O(n·32):
class BitTrie:
def __init__(self):
self.root = {}
def insert(self, num):
node = self.root
for i in range(31, -1, -1):
bit = (num >> i) & 1
if bit not in node:
node[bit] = {}
node = node[bit]
def max_xor(self, num):
node = self.root
xor = 0
for i in range(31, -1, -1):
bit = (num >> i) & 1
want = 1 - bit # prefer opposite bit for max XOR
if want in node:
xor |= (1 << i)
node = node[want]
else:
node = node[bit]
return xor
Classic Trie Interview Problems
| Problem | Approach | Complexity |
|---|---|---|
| Implement Trie (Prefix Tree) | Standard trie | O(m) per op |
| Design Search Autocomplete | Trie + DFS + sort by frequency | O(m + k log k) |
| Word Search II (board) | Trie + DFS backtracking | O(M·N·4^L) |
| Add and Search Word | Trie + recursive wildcard | O(m) / O(26^m) worst |
| Replace Words (sentence) | Trie prefix replacement | O(n·m) |
| Maximum XOR of Two Numbers | Binary Trie | O(n·32) |
| Palindrome Pairs | Trie + reverse words | O(n·m²) |
Interview Tips
- Recognize trie problems: “prefix,” “autocomplete,” “starts with,” “words sharing prefix”
- Dictionary (hash map) children is more flexible than array[26] for non-lowercase-alpha inputs
- Combine Trie with DFS for all-words-with-prefix; add a frequency counter for ranked autocomplete
- For Word Search II on a 2D board: build Trie from word list, DFS each cell, prune branches not in Trie
- Always mention the trade-off: Trie uses more memory than a hash set but enables O(m) prefix ops
{
“@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 so that all strings sharing a prefix share a common path. Use a Trie over a hash set when you need prefix operations: autocomplete, "find all words starting with X," or longest common prefix. A hash set gives O(1) exact lookup but O(n) for prefix queries; a Trie gives O(m) for both exact lookup and prefix traversal where m is word length.” }
},
{
“@type”: “Question”,
“name”: “How do you implement autocomplete using a Trie?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Insert all words into the Trie. For a given prefix, traverse the Trie to the last character of the prefix. Then DFS from that node to collect all complete words (nodes where is_end=True). For ranked results, store a frequency count at each terminal node and return the top-k by frequency using a max-heap.” }
},
{
“@type”: “Question”,
“name”: “How does the Trie-based solution for Word Search II work?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Build a Trie from the word list. Then DFS from each cell of the board, following only branches that exist in the Trie. When you reach a Trie node with is_end=True, you found a word. After finding a word, clear its is_end flag to avoid duplicates. This is much faster than checking each word separately because the Trie prunes dead-end paths early.” }
}
]
}