A trie — also called a prefix tree — stores a set of strings by sharing their common prefixes along a tree of characters. Each edge is one character, and a path from the root spells out a prefix. It turns "does any word start with ca?" into an O(L) walk down the tree, which is why it shows up in autocomplete, spell-checkers, and word-search puzzles.
This guide covers the trie data structure end to end for the trie coding interview: the node layout, insert/search/startsWith, when to reach for it, a clean Python implementation, and three worked problems with complexity.
The structure
A trie is made of nodes. Each node holds a map from a character to a child node, plus a boolean flag marking whether a word ends at that node. The root represents the empty prefix. Walking c → a → t and finding the flag set at the last node means "cat" was inserted; if the flag is unset there, "cat" is only a prefix of some longer word.
search("ca") will wrongly return true just because "cat" exists.
When to recognize this pattern
- Prefix queries. Autocomplete, "words starting with X", or repeated
startsWithchecks over a fixed dictionary. - Dictionary + wildcards. Word-dictionary designs where search must handle
.as "any character." - Many words, one scan. Grid problems (Word Search II) where you match a whole word list at once instead of one word at a time.
- Prefix replacement. Replacing words by their shortest root, as in the "replace words" problem.
Trie vs a hash set of words
A hash set answers exact membership in O(L), but it is blind to prefixes: to ask "how many words start with ca?" you would scan every key. A trie shares prefixes structurally, so startsWith is O(L) and you can enumerate every word under a prefix by walking the subtree. In an interview, the tell is repetition: if the same dictionary is queried many times, or if you need to answer prefix questions rather than exact lookups, the trie's one-time build cost pays for itself and every later query drops to the length of the key.
| Operation | Hash set of words | Trie |
|---|---|---|
| Exact search | O(L) | O(L) |
| Prefix check (startsWith) | O(total chars) | O(L) |
| Enumerate words with a prefix | Full scan | Subtree walk |
| Space | O(total chars) | O(total chars), shared prefixes save some |
A clean Python implementation
This is the standard "Implement Trie" answer — a TrieNode with a children dict and an is_word flag, plus insert/search/startsWith.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_word = 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_word = True
def _walk(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def search(self, word):
node = self._walk(word)
return node is not None and node.is_word
def startsWith(self, prefix):
return self._walk(prefix) is not NoneEach operation is O(L) in the key length, independent of how many words the trie holds. Space is O(total characters inserted).
Worked examples
Add and search word (with wildcards)
Problem: Support addWord and search, where a search string may contain . matching any single character.
Insert is the standard walk. Search becomes a DFS: on a ., recurse into every child.
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_word = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_word
ch = word[i]
if ch == '.':
return any(dfs(child, i + 1) for child in node.children.values())
return ch in node.children and dfs(node.children[ch], i + 1)
return dfs(self.root, 0)O(L) for a concrete word; a wildcard-heavy query can branch up to O(26L) in the worst case, but real inputs stay close to linear.
Word Search II
Problem: Given a grid of letters and a word list, return every word found by connecting adjacent cells.
Build a trie of the word list, then DFS the grid once, pruning any branch whose prefix isn't in the trie. Marking a node's word and removing it after a hit avoids duplicates.
def findWords(board, words):
root = TrieNode()
for w in words:
node = root
for ch in w:
node = node.children.setdefault(ch, TrieNode())
node.word = w # store full word at the end
rows, cols, found = len(board), len(board[0]), []
def dfs(r, c, node):
ch = board[r][c]
nxt = node.children.get(ch)
if not nxt:
return
if getattr(nxt, 'word', None):
found.append(nxt.word)
nxt.word = None # avoid duplicates
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 # restore
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return foundThe trie is what makes this tractable: one grid traversal checks every word at once and abandons dead prefixes immediately, instead of re-searching per word.
Replace Words
Problem: Given a dictionary of roots and a sentence, replace each word by the shortest root that is a prefix of it.
Insert all roots, then for each word walk the trie and stop at the first end-of-word node.
def replaceWords(dictionary, sentence):
root = TrieNode()
for w in dictionary:
node = root
for ch in w:
node = node.children.setdefault(ch, TrieNode())
node.is_word = True
def shortest_root(word):
node = root
prefix = []
for ch in word:
if ch not in node.children:
break
node = node.children[ch]
prefix.append(ch)
if node.is_word:
return ''.join(prefix)
return word
return ' '.join(shortest_root(w) for w in sentence.split())O(total characters) across all roots and words. Returning at the first is_word guarantees the shortest matching root.
Common pitfalls
- No end-of-word flag. Without it,
searchcan't tell a stored word from a prefix — the single most common trie bug. - Confusing search with startsWith.
searchrequires the flag at the final node;startsWithonly requires the path to exist. - Rebuilding the trie per query. Build it once, reuse it — the whole point is amortizing prefix work.
- Forgetting to backtrack in grid DFS. Restore the cell after recursion or you corrupt other paths.
Reach for the right data structure, live
CoPilot Interview is a desktop AI interview assistant that recognizes when a problem is a trie, sliding window, or graph — and shows working code with Big-O in about 4 seconds during real Zoom and Teams calls. Free tier for Windows and macOS.
See the coding interview copilotFAQ
When should I use a trie?
Reach for a trie when the problem is about prefixes over a set of strings — autocomplete, prefix matching, word dictionaries with wildcard search, or scanning a grid for many words at once. If you find yourself checking whether many strings share a starting sequence, a trie usually beats a hash set.
How does a trie differ from a hash set of words?
A hash set answers exact-membership in O(L) but knows nothing about prefixes. A trie shares common prefixes across words, so it answers startsWith in O(L) and lets you enumerate every word under a prefix, which a hash set cannot do without scanning everything.
What is the time complexity of trie operations?
Insert, search, and startsWith each run in O(L) where L is the length of the key, independent of how many words the trie holds. Space is O(total characters) in the worst case, though shared prefixes reduce it in practice.
Why is a trie faster than a hash set for Word Search II?
A trie lets a single DFS over the grid check all target words at once and prune a branch the moment no word shares the current prefix. A hash set would force you to search the grid separately for each word, which is far slower.
What is the most common trie bug?
Forgetting the end-of-word marker. Without a boolean flag on the terminal node, search cannot distinguish a full word from a mere prefix, so it returns true for prefixes that were never actually inserted.