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_xorSee also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Databricks Interview Prep