Trie Fundamentals and Implementation
A trie (prefix tree) stores strings character by character, sharing prefixes among strings. Each node represents one character; the path from root to a node spells a prefix. A node marked as end_of_word indicates a complete word ends there. Time complexity: insert, search, startsWith — all O(L) where L is the string length. Space: O(total characters across all words) — efficient when many strings share prefixes. Use cases: autocomplete (find all words with a prefix), spell checking, IP routing (longest prefix match), word search in a grid, XOR maximum (binary trie).
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False
self.count = 0 # how many words pass through this node
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.count += 1
node.is_end = True
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, prefix: str):
node = self.root
for c in prefix:
if c not in node.children:
return None
node = node.children[c]
return nodeWord Search II (LC 212) — DFS + Trie
Find all words in a 2D grid. Naive: run DFS from each cell for each word. With Trie: insert all words into a trie. DFS from each cell, following the trie — prune when no trie path matches. Pruning: when a trie node has no children, no word can extend from this path.
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
trie = Trie()
for w in words:
trie.insert(w)
rows, cols = len(board), len(board[0])
result = set()
def dfs(node, r, c, path):
if node.is_end:
result.add(path)
board[r][c], temp = '#', 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:
ch = board[nr][nc]
if ch != '#' and ch in node.children:
dfs(node.children[ch], nr, nc, path + ch)
board[r][c] = temp # restore
for r in range(rows):
for c in range(cols):
ch = board[r][c]
if ch in trie.root.children:
dfs(trie.root.children[ch], r, c, ch)
return list(result)Design Search Autocomplete System (LC 642)
Each trie node stores the top-3 hottest sentences (by frequency) that pass through it. On insert: update frequencies, propagate top-3 up the trie. On search prefix: traverse to the prefix node, return its stored top-3.
import heapq
class AutocompleteSystem:
def __init__(self, sentences: list[str], times: list[int]):
self.root = TrieNode()
self.freq = {}
self.prefix = ""
for s, t in zip(sentences, times):
self.freq[s] = t
self._add(s, t)
def _add(self, sentence: str, freq: int):
node = self.root
for c in sentence:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
# Maintain top-3 by frequency
node.top = sorted(
set(node.top + [(freq, sentence)]),
key=lambda x: (-x[0], x[1])
)[:3]
def input(self, c: str) -> list[str]:
if c == '#':
self.freq[self.prefix] = self.freq.get(self.prefix, 0) + 1
self._add(self.prefix, self.freq[self.prefix])
self.prefix = ""
return []
self.prefix += c
node = self.root
for ch in self.prefix:
if ch not in node.children:
return []
node = node.children[ch]
return [s for _, s in node.top]XOR Maximum with Binary Trie (LC 421)
Maximum XOR of two numbers in an array. Insert all numbers into a binary trie (bit by bit, from MSB to LSB). For each number, greedily find the number in the trie that maximizes XOR (always try to take the opposite bit).
def find_maximum_xor(nums: list[int]) -> int:
# Build binary trie
root = [None, None] # [bit=0 child, bit=1 child]
for n in nums:
node = root
for i in range(31, -1, -1):
bit = (n >> i) & 1
if node[bit] is None:
node[bit] = [None, None]
node = node[bit]
max_xor = 0
for n in nums:
node = root
curr_xor = 0
for i in range(31, -1, -1):
bit = (n >> i) & 1
want = 1 - bit # prefer opposite bit for max XOR
if node[want] is not None:
curr_xor |= (1 << i)
node = node[want]
else:
node = node[bit]
max_xor = max(max_xor, curr_xor)
return max_xor
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the time and space complexity of a trie vs. a hash set for string lookup?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Hash set: O(L) time per lookup (hash function processes each character), O(total characters) space, but does not support prefix queries. Trie: O(L) time per lookup, O(total characters * alphabet_size) space (worst case each node allocates space for all possible children). In practice, tries use a dictionary for children (not an array), reducing space to O(total characters). The key advantage of tries: prefix queries are O(P) where P is the prefix length — a hash set cannot do prefix queries at all without scanning all strings. For autocomplete, spell checking, or IP routing: trie wins. For simple exact-match lookup with many strings: hash set is simpler and more memory-efficient.”}},{“@type”:”Question”,”name”:”How does the Word Search II trie pruning improve performance over brute force?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Brute force: for each of W words, run a DFS from each of R*C cells — O(W * R * C * 4^L) total. With Trie: insert all W words into a trie. Run DFS from each cell once, following the trie simultaneously. The key optimization: if the current path prefix does not exist in the trie (no children matching the next character), prune the DFS immediately — do not explore that branch. This eliminates all DFS paths that cannot lead to any word in the word list. Additional optimization: delete leaf nodes (end_of_word markers) from the trie as words are found — prevents finding the same word multiple times and prunes exhausted branches. Overall: O(R * C * 4^L) in the worst case, but practical performance is much better due to early pruning.”}},{“@type”:”Question”,”name”:”How does the binary trie find the maximum XOR in O(n log(max_value))?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”For each number n, we want to find the number in the array that, XORed with n, gives the maximum result. XOR is maximized when bits differ. Binary trie stores each number bit by bit from MSB to LSB. For each number n: traverse the trie greedily — at each bit position, if the opposite bit (1-bit when n has 0, or 0-bit when n has 1) exists in the trie, take it (sets the XOR bit to 1). Otherwise, take the same bit (XOR bit is 0). This greedy is correct because higher bits contribute more to the XOR value — maximizing higher bits first is always optimal. Total time: O(n) to build the trie, O(n * 32) to find maximum XOR for all n — O(n log(max_value)) where log(max_value) = 32 for 32-bit integers.”}},{“@type”:”Question”,”name”:”What is a compressed trie (radix tree) and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A standard trie has one node per character, leading to long chains for strings with no shared prefixes. A compressed trie (radix tree, Patricia trie) compresses chains of single-child nodes into one node with a label (the whole substring). Example: "interview" and "internet" share "inter" — one node for "inter" with two children "view" and "net". Space reduction: O(n) nodes instead of O(total characters) where n = number of strings. Lookup: still O(L) but with fewer node traversals. Used in: IP routing tables (CIDR prefix matching), HTTP routing (URL path dispatch), database index structures. For interview problems, the standard (uncompressed) trie is usually sufficient. Mention compressed tries when asked about memory optimization or when the strings are long with few shared prefixes.”}},{“@type”:”Question”,”name”:”How does a trie implement the "count words with prefix" and "sum of prefix scores" operations?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Count words with prefix: store a count at each trie node representing how many complete words pass through it (increment on each insert). Prefix query: traverse to the prefix node, return node.count. This is O(P) per query. Sum of prefix scores (LC 2416): for each word, sum the count values at each node along its path. Each word's score = sum of (count at each character node from root to end). Compute by inserting all words first, then traversing each word again and summing node counts. Space: O(total characters). Time: O(total characters) for build + O(total characters) for queries. This pattern generalizes: any per-prefix statistic can be maintained by storing it at each trie node and updating on insert.”}}]}
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Databricks Interview Prep