AdvancedData Structures & Algorithms · Lesson 27 of 29 · Updated ·
Tries (Prefix Trees) — Insert, Search, Prefix Count and Autocomplete
When you type "ca" in a phone's contact search, it shows "Carol", "Catherine" and "Cathy" at once. The phone is answering a prefix question: which stored words start with these letters? A hash set can tell you whether one exact word exists, but it cannot answer prefix questions quickly. A trie (say "try", from retrieval), also called a prefix tree, is built exactly for this.
1. What a trie looks like
A trie is a tree where:
- the root is empty;
- each edge (or child node) stands for one letter;
- the path from the root to a node spells a prefix;
- a node is marked end of word if a stored word finishes there.
Here are the words car, card, care, cat, do, dog:
Four words share the path c → a. They are stored once, not four times. Notice that car ends at r, but r still has children (d and e). That is why we need the end-of-word mark: reaching a node does not mean a word ends there.
2. Insert and search
Each node keeps a map from letter to child node, an end flag, and (for later) a count of how many words pass through it.
class TrieNode:
def __init__(self):
self.kids = {} # letter -> TrieNode
self.end = False # does a word end here?
self.count = 0 # how many words pass through this node
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.kids:
node.kids[ch] = TrieNode()
node = node.kids[ch]
node.count += 1
node.end = True
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node.kids:
return None
node = node.kids[ch]
return node
def search(self, word): # exact word stored?
node = self._walk(word)
return node is not None and node.end
def starts_with(self, prefix): # any word with this prefix?
return self._walk(prefix) is not None
t = Trie()
for w in ["car", "card", "care", "cat", "do", "dog"]:
t.insert(w)
print(t.search("car"), t.search("ca"), t.search("cart"))
print(t.starts_with("ca"), t.starts_with("dx"))
True False False
True False
search("ca") is False because no word ends at a, even though the path exists. starts_with("ca") only needs the path.
Cost. Insert, search and starts-with all take O(L) time, where L is the length of the word — no matter how many words are stored. Space is at most the total number of letters across all words, and less when prefixes are shared.
3. Prefix count and autocomplete
Because each node stores count, "how many words start with this prefix?" is just: walk down the prefix and read the count. For autocomplete, walk down the prefix, then do a DFS below that node and collect every word that ends there.
class TrieNode:
def __init__(self):
self.kids, self.end, self.count = {}, False, 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.kids.setdefault(ch, TrieNode())
node.count += 1
node.end = True
def _walk(self, s):
node = self.root
for ch in s:
node = node.kids.get(ch)
if node is None:
return None
return node
def count_prefix(self, prefix):
node = self._walk(prefix)
return node.count if node else 0
def autocomplete(self, prefix, limit=10):
node, out = self._walk(prefix), []
def dfs(n, word):
if len(out) == limit:
return
if n.end:
out.append(word)
for ch in sorted(n.kids): # sorted: alphabetical suggestions
dfs(n.kids[ch], word + ch)
if node:
dfs(node, prefix)
return out
t = Trie()
for w in ["car", "card", "care", "cat", "do", "dog"]:
t.insert(w)
print(t.count_prefix("car"), t.count_prefix("d"), t.count_prefix("z"))
print(t.autocomplete("ca"))
print(t.autocomplete("ca", limit=2))
3 2 0
['car', 'card', 'care', 'cat']
['car', 'card']
4. The same trie in Java
For lowercase English words, an array of 26 children is faster than a map: the child for letter c is at index c - 'a'.
public class Main {
static class Node {
Node[] kids = new Node[26];
boolean end;
int count;
}
static Node root = new Node();
static void insert(String w) {
Node n = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (n.kids[i] == null) n.kids[i] = new Node();
n = n.kids[i];
n.count++;
}
n.end = true;
}
static Node walk(String s) {
Node n = root;
for (char c : s.toCharArray()) {
n = n.kids[c - 'a'];
if (n == null) return null;
}
return n;
}
public static void main(String[] args) {
for (String w : new String[]{"car", "card", "care", "cat", "do", "dog"}) insert(w);
Node a = walk("car"), b = walk("ca"), c = walk("dot");
System.out.println((a != null && a.end) + " " + (b != null && b.end) + " " + (c != null));
System.out.println(walk("ca").count + " " + walk("do").count);
}
}
true false false
4 2
The array version uses 26 references per node even when most are empty, so it trades memory for speed. A map per node uses less memory when the alphabet is large (for example, Unicode text).
5. Trie or hash set?
| Question | Hash set | Trie |
|---|---|---|
| Is this exact word stored? | O(L) on average | O(L) |
| How many words start with "ca"? | must check every word | O(L) |
| List words with a prefix in sorted order | check and sort every word | DFS below one node |
| Memory | one entry per word | shared prefixes, but node overhead |
Typical trie problems: implement a trie, autocomplete or search suggestions, word search on a grid with many words (put the words in a trie so the DFS can stop early), longest common prefix, and replacing words by their shortest root word.
Common mistakes
- Treating "the path exists" as "the word exists". Always check the
endflag insearch. - Forgetting to increase
counton every node along the path, so prefix counts come out wrong. - Using
c - 'a'when the input can contain capital letters, digits or spaces, which gives a negative or too-large index. - Building a trie when the problem only ever asks exact-match questions; a hash set is simpler then.
Quick recap
- A trie stores words letter by letter; words with a common prefix share one path.
- Each node has children, an end-of-word flag and, optionally, a pass-through count.
- Insert, search and starts-with are O(L) for a word of length L.
- Prefix count: walk the prefix, read
count. Autocomplete: walk the prefix, then DFS. - Use 26-slot arrays for lowercase letters (fast) or a map per node (flexible).