Tries (Prefix Trees)
A trie stores strings character by character so that prefix lookups cost O(length of the prefix), not O(number of words). Working code, autocomplete example and when a trie is the wrong tool.
A trie, or prefix tree, stores strings one character per edge, so words that share a prefix share a path from the root. Insert, search and prefix lookup take O(L) time, where L is the string length, regardless of how many words are stored. Interviewers expect the end-of-word flag, since a prefix path can exist without being a word.
A trie (prefix tree) stores words one character per node, so words that share a prefix share a path from the root. Insert, search and prefix lookup all take O(L), where L is the length of the string, independent of how many words are stored.
- Trie insert, search and prefix checks each take O(L) time for a string of length L, independent of how many words are stored.
- A trie needs an end-of-word flag because a path can exist for a prefix that is not a word: after adding car, the path for ca exists but has('ca') is False.
- Listing all words under a prefix in a trie costs O(L) to reach the prefix node plus the size of the output produced.
- In the worst case a trie uses one node per stored character, and with array nodes each node also holds one slot per alphabet symbol, such as 26 for lowercase English.
- A radix tree, or compact trie, merges chains of single-child nodes into one edge labelled with a substring, which saves most of a trie's memory.
01The problem a trie solves
Suppose you store a dictionary of words and a user types "car". A hash set can tell you whether "car" is a word in O(1), but it cannot list the words that start with "car" without checking each one. A sorted array can find the range with binary search, but inserts are O(n).
A trie makes this natural. The root is empty. Each edge is a character. A word is a path from the root, and a flag on the last node says "a word ends here". Words with a common prefix share the path for that prefix, so "car", "card", "care" and "cat" share the nodes for c and a.
02Building one
class Trie:
def __init__(self):
self.children = {}
self.end = False
def add(self, word):
node = self
for ch in word:
node = node.children.setdefault(ch, Trie())
node.end = True
def _find(self, prefix):
node = self
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def has(self, word):
node = self._find(word)
return bool(node and node.end)
def with_prefix(self, prefix):
out = []
def walk(node, acc):
if node.end:
out.append(acc)
for ch in sorted(node.children):
walk(node.children[ch], acc + ch)
start = self._find(prefix)
if start:
walk(start, prefix)
return out
t = Trie()
for w in ["car", "card", "care", "cat", "dog", "do"]:
t.add(w)
print(t.has("car"), t.has("ca")) # True False
print(t.with_prefix("car")) # ['car', 'card', 'care']
print(t.with_prefix("do")) # ['do', 'dog']
print(t.with_prefix("x")) # []Notice has("ca") is False. The path for "ca" exists, but nothing ends there. That is the whole reason for the end flag, and forgetting it is the most common bug.
03Complexity
Insert, search and checking a prefix each take O(L) for a word of length L. It makes no difference whether you store ten words or ten million. Compare that with a balanced tree of strings, where each comparison can itself cost O(L) and you do O(log n) of them.
Listing all words under a prefix costs O(L) to reach the prefix node, plus the size of the output you produce.
Space is the weak side. In the worst case, with no shared prefixes, a trie uses one node per character, and each node carries a map. Dictionary words share many prefixes, so real tries are smaller than that, but they are still far bigger than the raw text.
04Dict nodes or array nodes
If the alphabet is small and fixed, such as lowercase English letters, each node can hold an array of 26 child pointers. Lookup is an index, children[ord(ch) - 97], which is fast, but every node pays for 26 slots even if it has one child.
If the alphabet is large (Unicode, for example), a dict or hash map per node is the sensible choice, which is what the code above does.
Compressed variants exist. A radix tree (also called a compact trie) merges chains of single-child nodes into one edge labelled with a whole substring, which saves most of the memory. IP routing tables and some HTTP routers use this idea.
05Where tries are used
Autocomplete is the standard example: walk to the node for what the user has typed, then collect words below it. Production systems also store a score at each node (popularity) so they can return only the top few suggestions.
Spell checkers and word games such as Boggle use a trie to prune. If no word starts with the letters so far, stop exploring that path immediately. That cut turns an exponential search into something practical.
A second classic use is the maximum XOR of two numbers in an array. Store each number's bits in a binary trie from the most significant bit down, then for each number walk the trie choosing the opposite bit whenever it exists.
06When not to use a trie
If you never need prefix operations, use a hash set. It uses less memory and its lookups are O(L) as well, because hashing a string reads the whole string.
If the data is static and you only need prefix matches, a sorted array with two binary searches (one for the lower bound and one for the end of the prefix range) uses almost no extra memory.
Tries make sense when the set changes, prefix queries are frequent, and you want predictable O(L) behaviour.
07Common interview questions
Q: What is the time complexity of insert and search?
A: O(L) where L is the length of the word, regardless of how many words are stored.
Q: Why store an end-of-word flag?
A: Because a path can exist for a prefix that is not itself a word. "ca" is on the path to "car" but is not a word.
Q: How would you implement autocomplete?
A: Walk to the prefix node, then run a depth-first search below it to collect words. To return only the best few, store a frequency or score on word-ending nodes and keep a small heap.
Q: How do you delete a word?
A: Clear the end flag. Optionally remove nodes on the way back up that have no children and are not the end of another word.
Q: Trie versus hash map for a dictionary?
A: A hash map is better for exact membership. A trie is better when you need prefix search or ordered traversal.
Q: What is the space complexity?
A: In the worst case O(total characters stored) nodes, with no shared prefixes. With array nodes each node also holds one slot per alphabet symbol, so multiply by the alphabet size. Shared prefixes reduce it in practice.