A trie (prefix tree) is a tree where each node represents a character and the path from root to a node spells a prefix. Tries make prefix lookups O(m) where m is the string length — regardless of how many strings are stored. This is the data structure behind autocomplete, spell checking, IP routing tables, and DNS lookups. A dozen LeetCode medium/hard problems reduce to standard trie operations.
Trie Node and Implementation
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # marks end of a word
self.count = 0 # words ending here (for frequency)
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._traverse(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
return self._traverse(prefix) is not None
def _traverse(self, s: str):
node = self.root
for ch in s:
if ch not in node.children:
return None
node = node.children[ch]
return nodeTime: O(m) for all operations where m = word length. Space: O(ALPHABET_SIZE * m * n) for n words. In practice, use a dict for children (not a fixed-size array) when the alphabet is large.
Pattern 1: Autocomplete / Search Suggestions
Given a prefix, return all words with that prefix. Traverse to the prefix node, then DFS to collect all words ending in subtrees:
def autocomplete(self, prefix: str) -> list:
node = self._traverse(prefix)
if not node:
return []
results = []
self._dfs(node, list(prefix), results)
return results
def _dfs(self, node, path, results):
if node.is_end:
results.append("".join(path))
for ch, child in node.children.items():
path.append(ch)
self._dfs(child, path, results)
path.pop()For top-K suggestions by frequency: store a heap or sorted list at each node during insert. Or store word count and collect all matches, then sort. LeetCode 1268: Search Suggestions System.
Pattern 2: Word Search II (Multiple Words on a Grid)
Given a grid and a word list, find all words that exist in the grid following adjacent cells. Naive approach: BFS/DFS for each word independently = O(W * R * C * 4^L). Trie approach: build a trie from all words, then DFS on the grid using the trie to prune. When the current path is not a prefix of any word, stop early. This reduces total work from O(W * …) to O(R * C * 4^L) where the trie pruning cuts dead branches early.
def findWords(self, board, words):
trie = Trie()
for word in words:
trie.insert(word)
rows, cols = len(board), len(board[0])
result = set()
def dfs(node, r, c, path):
ch = board[r][c]
if ch not in node.children:
return
next_node = node.children[ch]
path.append(ch)
if next_node.is_end:
result.add("".join(path))
board[r][c] = "#" # mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
dfs(next_node, nr, nc, path)
board[r][c] = ch # restore
path.pop()
for r in range(rows):
for c in range(cols):
dfs(trie.root, r, c, [])
return list(result)Pattern 3: Replace Words (Root Prefix Replacement)
Given a list of root words and a sentence, replace each word in the sentence with its shortest root prefix from the list. Build a trie from roots. For each sentence word, traverse the trie: if you hit an is_end node before consuming the full word, that prefix is the root — use it. LeetCode 648.
def replaceWords(self, dictionary, sentence):
trie = Trie()
for root in dictionary:
trie.insert(root)
def get_root(word):
node = trie.root
for i, ch in enumerate(word):
if ch not in node.children:
break
node = node.children[ch]
if node.is_end:
return word[:i+1] # found shortest root
return word # no root found, keep original
return " ".join(get_root(w) for w in sentence.split())Pattern 4: Wildcard Search (. matches any character)
Design a data structure supporting add(word) and search(word) where . is a wildcard matching any character. LeetCode 211: Design Add and Search Words Data Structure. The trie handles . by branching into all children at that position:
def search(self, word: str) -> bool:
def dfs(node, i):
if i == len(word):
return node.is_end
ch = word[i]
if ch == ".":
return any(dfs(child, i+1) for child in node.children.values())
if ch not in node.children:
return False
return dfs(node.children[ch], i+1)
return dfs(self.root, 0)Pattern 5: XOR Maximization with Binary Trie
Find the maximum XOR of any two numbers in an array. LeetCode 421. Build a binary trie where each number is inserted as 32 bits from MSB to LSB. For each number, greedily choose the opposite bit at each level (to maximize XOR). If the desired bit exists in the trie, go that way; otherwise take what is available.
def findMaximumXOR(self, nums):
MAX_BITS = 31
root = {}
for num in nums:
node = root
for bit in range(MAX_BITS, -1, -1):
b = (num >> bit) & 1
if b not in node:
node[b] = {}
node = node[b]
max_xor = 0
for num in nums:
node = root
xor = 0
for bit in range(MAX_BITS, -1, -1):
b = (num >> bit) & 1
want = 1 - b # opposite bit maximizes XOR
if want in node:
xor = (xor << 1) | 1
node = node[want]
else:
xor = xor << 1
node = node[b]
max_xor = max(max_xor, xor)
return max_xorSpace Optimization: Compressed Trie (Patricia Trie)
A standard trie wastes space when there are long chains of nodes with a single child. A compressed trie (Patricia trie, radix tree) merges these chains: each edge stores a string (substring) instead of a single character. Insertion and lookup are still O(m) but space is O(n) for n strings instead of O(n * m). Used in IP routing tables (Linux kernel uses a Patricia trie for the FIB), DNS implementations, and autocomplete backends serving millions of strings.
When to Use a Trie
- Prefix queries: “does any stored string start with X?” — O(m) vs O(n*m) with a list
- Autocomplete and spell correction
- Word search on a grid with multiple target words
- Bitwise XOR problems (binary trie)
- IP address longest prefix matching (radix trie)
Prefer a hash set when you only need exact matches. Use a trie when prefix relationships matter.
Frequently Asked Questions
What is the time and space complexity of a trie?
Insert, search, and startsWith all run in O(m) time where m is the length of the string — regardless of how many strings are stored. This is a key advantage over a hash set, which has O(m) time per operation due to hashing but does not support prefix queries at all. Space complexity is O(ALPHABET_SIZE * m * n) for n strings of average length m with an alphabet of size A. For lowercase English letters (A=26) and a hash-map-based children structure, space is O(m * n) total — each character of each inserted string gets its own node. In practice, a compressed trie (radix tree) reduces space by merging chains of single-child nodes, achieving O(n * max_word_length) nodes in the worst case but much less for real word sets where strings share long prefixes.
When should you use a trie instead of a hash set?
Use a trie when you need prefix queries ("does any stored string start with X?"), autocomplete suggestions ("return all strings with this prefix"), or lexicographic ordering of stored strings. A hash set only supports exact membership tests in O(m) time per lookup. A trie supports startsWith in O(m) and getAllWithPrefix in O(m + K) where K is the number of matching strings — a hash set would require scanning all n stored strings for prefix matches, taking O(n * m) time. Use a hash set when you only need exact lookups, since hash sets have lower memory overhead and simpler implementation. The trie shines for: autocomplete systems, IP routing longest-prefix matching, spell checkers, and any scenario where you need to navigate a shared-prefix structure.
How do you delete a word from a trie?
Deletion requires three steps: (1) Verify the word exists. (2) Unmark the is_end flag at the terminal node. (3) Optionally prune leaf nodes that no longer form any word. Pruning is the tricky part: traverse from the terminal node back to the root, deleting each node that has no children and is not marked is_end. A recursive implementation handles pruning naturally — after recursing into the child, check if the child node is now empty (no children, not end-of-word) and delete it. This ensures the trie does not accumulate orphaned nodes after many deletions. In interview settings, if deletion is required, confirm whether pruning is necessary — often the simpler unmark-only approach is acceptable.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the time and space complexity of a trie?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Insert, search, and startsWith all run in O(m) time where m is the length of the string — regardless of how many strings are stored. This is a key advantage over a hash set, which has O(m) time per operation due to hashing but does not support prefix queries at all. Space complexity is O(ALPHABET_SIZE * m * n) for n strings of average length m with an alphabet of size A. For lowercase English letters (A=26) and a hash-map-based children structure, space is O(m * n) total — each character of each inserted string gets its own node. In practice, a compressed trie (radix tree) reduces space by merging chains of single-child nodes, achieving O(n * max_word_length) nodes in the worst case but much less for real word sets where strings share long prefixes.”
}
},
{
“@type”: “Question”,
“name”: “When should you use a trie instead of a hash set?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use a trie when you need prefix queries (“does any stored string start with X?”), autocomplete suggestions (“return all strings with this prefix”), or lexicographic ordering of stored strings. A hash set only supports exact membership tests in O(m) time per lookup. A trie supports startsWith in O(m) and getAllWithPrefix in O(m + K) where K is the number of matching strings — a hash set would require scanning all n stored strings for prefix matches, taking O(n * m) time. Use a hash set when you only need exact lookups, since hash sets have lower memory overhead and simpler implementation. The trie shines for: autocomplete systems, IP routing longest-prefix matching, spell checkers, and any scenario where you need to navigate a shared-prefix structure.”
}
},
{
“@type”: “Question”,
“name”: “How do you delete a word from a trie?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Deletion requires three steps: (1) Verify the word exists. (2) Unmark the is_end flag at the terminal node. (3) Optionally prune leaf nodes that no longer form any word. Pruning is the tricky part: traverse from the terminal node back to the root, deleting each node that has no children and is not marked is_end. A recursive implementation handles pruning naturally — after recursing into the child, check if the child node is now empty (no children, not end-of-word) and delete it. This ensures the trie does not accumulate orphaned nodes after many deletions. In interview settings, if deletion is required, confirm whether pruning is necessary — often the simpler unmark-only approach is acceptable.”
}
}
]
}