TrieTries
One character per level, shared prefixes.
Used for: Autocomplete, spell check, IP routing tables
01Why it exists
The user types "alg" and every word beginning with alg has to appear at once. The dictionary holds a few hundred thousand words, so scanning it on each keystroke is far too slow, and a hash table can only look up a complete key.
Why this fitsA trie stacks words that share a prefix onto the same path. Three steps take you to "alg", and everything beneath that node is the answer — at a cost that has nothing to do with the size of the dictionary.
Every word in a document has to be checked against a dictionary, or a block of text has to be scanned for any occurrence of any banned word.
Why this fitsLooking up a word of length L takes L steps. When many patterns are matched at once, building them all into one tree lets a single pass over the text compare against every pattern simultaneously — the foundation of Aho-Corasick.
A routing table holds a few hundred thousand rules, every packet needs the rule with the longest prefix match, and the router has to keep up with a million packets a second.
Why this fitsTreat the IP as a bit string in a trie and walk down along the packet's bits; the deepest valid node you reach is the longest prefix. This is the classic use of a binary trie, or radix tree.
Reach for it when you see:Prefix, starts with, autocomplete, many strings sharing a prefix, longest prefix match, dictionary.
02The core idea
A trie (the name comes from retrieval) is a tree with characters on its edges. Start at the root, string together the characters along the edges, and the path to any node spells out a prefix. Strings that share a prefix share a path: car, cat and cart need only one c-a route before they branch apart. Each node also carries an end marker meaning "a string finishes exactly here", which is what separates "ca is only a prefix" from "car is a word".
Inserting, looking up and testing a prefix all amount to taking one step down per character of the string, so the cost is the length of that string, O(L), no matter how many strings the tree holds. That is the difference from a hash table: a hash table can also look up a complete word in O(L), but it knows nothing about prefixes, whereas once a trie has walked to the prefix's node, the whole subtree underneath is the answer.
The price is space. Every node needs a table of children. A small alphabet (26 lowercase letters) can use a fixed array, which makes each step O(1) at the cost of 26 pointers per node; a large alphabet (Unicode) calls for a hash table, which saves space but is a little slower. In practice tries are also compressed, collapsing any chain of single-child nodes into one string segment — that is a radix tree, and it is what routing tables and many file systems are built on.
03The algorithm
- 1Node structure: a table of children (a
dict, or an array of length 26) plus anis_endboolean. The root stands for the empty string. - 2Insert: start at the root and, for each character, create the matching child if it does not exist, then step into it. Mark the final node
is_end = True. - 3Search for a word: follow the characters, and any step you cannot take means the word is absent; once you arrive, you still have to check
is_end. Search for a prefix: arriving at all is enough. - 4Autocomplete: walk to the prefix's node, then DFS that subtree, collecting a word every time you hit
is_end. - 5When the alphabet is small and fixed, store children in an array for faster steps; otherwise use a hash table. With very large numbers of strings, consider compressing into a radix tree.
04Interactive demo
Insert car, cat, cart and dog, and watch the shared c-a path get reused. Then look up the prefix ca for autocomplete, and check whether ca and cart are complete words on their own. The green nodes are the ones carrying an end marker.
05Code
Insert, word lookup, prefix lookup and autocomplete. The Python version stores children in a dict; the C++ version shows the fixed-array form for a lowercase alphabet.
class TrieNode:
def __init__(self):
self.children = {} # character -> TrieNode
self.is_end = False # does a word end right here?
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: # no such edge yet, so open one
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def _walk(self, s):
"""Follow s as far as it goes; return None if the path runs out"""
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
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 autocomplete(self, prefix):
"""List every word starting with prefix: walk to the prefix, then collect with DFS"""
node = self._walk(prefix)
out = []
def dfs(n, path):
if n.is_end:
out.append(path)
for ch, child in sorted(n.children.items()):
dfs(child, path + ch)
if node:
dfs(node, prefix)
return out
t = Trie()
for w in ["car", "cat", "cart", "dog"]:
t.insert(w)
print(t.search("ca"), t.starts_with("ca")) # False True
print(t.autocomplete("ca")) # ['car', 'cart', 'cat']06Practice
- LeetCode 208Implement Trie (Prefix Tree)Medium
- LeetCode 211Design Add and Search Words (DFS with a wildcard)Medium
- LeetCode 1268Search Suggestions System (autocomplete)Medium
- LeetCode 212Word Search II (trie plus grid backtracking)Hard
- LeetCode 648Replace Words (shortest prefix)Medium