Trie
01 / The one-sentence essence
Store a set of strings on a tree of characters — each node is a prefix, each edge is a character, and a special end-of-word marker distinguishes "this prefix is also a stored word" from "this is just a prefix on the way to longer words."
Problemstore + search words on a prefix treeOps7Split4 insert · 3 search
Empty trie — just the root. Each operation walks the tree one character at a time.
step
0 / 35
op
—
nodes
1
last result
—
0 / 35
02 / The pattern signature
# a trie node is a map + an "is this a word ending" flagclass Node:children: dict[char, Node] = {}is_end: bool = False def insert(word):node = rootfor ch in word:if ch not in node.children:node.children[ch] = Node()node = node.children[ch]node.is_end = True def search(word):node = walk(word) # follow each char or return None on missreturn node is not None and node.is_end
03 / When to recognize this pattern
"prefix queries"
The problem cares about prefixes, not just full matches — autocomplete, longest-common-prefix, "all words starting with X". A hash set can't answer these in better than linear scan.
"dictionary of words"
A fixed dictionary you'll query many times. The dictionary is the trie; queries are walks. Build cost is amortized over every query.
"alphabet-bounded keys"
Each step branches on one of a small fixed set of values — lowercase letters (26), digits (10), IP octets (256). When the alphabet is unbounded or continuous, a different structure fits better.
"shared structure"
Words like
"car", "card", "care", "cart" share the same first three nodes — the trie stores that prefix once. If most words don't share prefixes, the trie is a thin wrapper around a hash set and the win shrinks.04 / Common pitfalls
Forgetting the end-of-word marker.
Reaching the last character of a search word isn't enough — you also need the node to be marked as
is_end. If you skip the marker, search("ca") will succeed after inserting "cat", which is wrong. The marker is what turns a prefix tree into a word set.Confusing search with startsWith.
search(w) requires the terminal node to be marked. startsWith(p) only requires that the walk completes — no end-of-word check. The same walking code underlies both; the post-condition differs by one line.Using a 26-slot array when keys aren't bounded.
A fixed
children[26] array is fast and cache-friendly for lowercase-only alphabets but becomes a memory disaster on larger alphabets (Unicode, byte streams). Default to a hash map; switch to a fixed array only when the alphabet is small and the inner loop is hot.05 / Go practice — on LeetCode
medium11
01Implement Trie (Prefix Tree)— LC 208→02Design Add and Search Words Data Structure— LC 211→03Maximum XOR of Two Numbers in an Array— LC 421→04Replace Words— LC 648→05Implement Magic Dictionary— LC 676→06Longest Word in Dictionary— LC 720→07Short Encoding of Words— LC 820→08Camelcase Matching— LC 1023→09Search Suggestions System— LC 1268→10Longest Word With All Prefixes— LC 1858→11Find The Original Array of Prefix Xor— LC 2433→
hard9
01Word Break II— LC 140→02Word Search II— LC 212→03Word Squares— LC 425→04Concatenated Words— LC 472→05Design Search Autocomplete System— LC 642→06Prefix and Suffix Search— LC 745→07Maximum XOR With an Element From Array— LC 1707→08Count Pairs With XOR in a Range— LC 1803→09Maximum Genetic Difference Query— LC 1938→