Tries (Prefix Trees)
Share prefixes to search a dictionary by character. The structure behind autocomplete and word-search boards.
A hash set can tell you whether a full word exists. A trie can tell you whether any word starts with a prefix. That difference is everything for autocomplete, dictionary search, and board problems where you build a word one character at a time.
A trie stores shared prefixes once. If car, card, and care are all in the dictionary, the path c -> a -> r is shared; only the endings branch. You pay extra pointers to avoid repeatedly scanning or slicing strings.
The mental model
Each node is a dictionary of outgoing character edges plus a flag saying whether a word ends there.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = FalseInsertion walks one character at a time, creating missing nodes. Search walks the same path and then checks the ending flag. Prefix search is identical except it does not require is_end at the final node.
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def search(self, word):
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):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return TrueFor a word of length L, insert, search, and starts_with are O(L). A hash set is also fast for exact full-word lookup, but it cannot answer “does any word start with this partial path?” without checking many words. A trie bakes that prefix question into the structure.
Pattern recognition
Variations
Worked problems
These move from the basic API to the reason tries are worth knowing: pruning a large branching search.
Implement Trie
Design a prefix tree with three operations: insert a word, check whether a full word exists, and check whether any inserted word starts with a prefix.
Approach. Use one root node. Every operation walks characters from the root. insert creates missing nodes and marks the final node as a word ending. search requires that final flag; starts_with only requires the path to exist.
Show solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
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):
node = self._walk(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, text):
node = self.root
for ch in text:
if ch not in node.children:
return None
node = node.children[ch]
return nodeComplexity. Each operation is O(L) time for input length L. Space is O(T) for the total number of characters inserted, minus shared prefixes.
Design Add and Search Words Data Structure
Design a word dictionary that supports adding words and searching patterns where . can match any single character.
Approach. Normal letters follow one trie edge. A dot branches to every child, so search becomes DFS over (node, index). The pattern matches only if some branch consumes every character and lands on a node marked as a word ending.
Show solution
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def add_word(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
def search(self, pattern):
def dfs(node, i):
if i == len(pattern):
return node.is_end
ch = pattern[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)Complexity. add_word is O(L). Search is O(L) without wildcards, and in the worst case can branch across many trie nodes when the pattern contains dots. Space is O(T) for inserted characters.
Word Search II
Given a grid of letters and a list of words, return every word that can be formed by walking horizontally or vertically through adjacent cells without reusing a cell in the same word.
Approach. Put the dictionary in a trie, then start DFS from every board cell. As you move, follow the matching trie child. If a character is not a child, stop that branch immediately; no dictionary word has that prefix. Store the completed word on the terminal trie node so you can add it without rebuilding strings.
Show solution
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def find_words(board, words):
root = TrieNode()
for word in words:
node = root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.word = word
rows, cols = len(board), len(board[0])
ans = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node.children:
return
nxt = node.children[ch]
if nxt.word is not None:
ans.append(nxt.word)
nxt.word = None
board[r][c] = "#"
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, nxt)
board[r][c] = ch
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return ansComplexity. Building the trie is O(total word characters). The board search is bounded by O(rows · cols · 4^L) in the worst case for maximum word length L, but trie pruning cuts off branches as soon as no word has the current prefix.