Tries (Prefix Trees)
A tree keyed by characters that makes prefix search, autocomplete and word lookup cost O(length of the word), independent of dictionary size.
intermediate40 min#trie#prefix-tree#autocomplete#strings
Prerequisites: Trees and Binary Search Trees, Hash Tables
Why it matters
Autocomplete, spell checkers, IP routing tables, and word games all ask the same question: "which stored strings start with this prefix?" A hash table answers "is this exact word present?" in O(L) for a word of length L, but it cannot list words by prefix without scanning everything. A trie (pronounced "try", from retrieval) is built for prefixes, and its lookup cost depends only on the length of the query, not on how many words are stored.
Intuition
Open a paper dictionary. You do not read from page one; you narrow down by first letter, then second letter, then third. A trie encodes that narrowing as a tree. Each edge is a character, each path from the root spells a prefix, and words that share a beginning share the same path, so the prefix is stored only once.
root
|-- c
| `-- a
| |-- r * "car"
| | |-- d * "card"
| | `-- e * "care"
| `-- t * "cat"
`-- d -- o -- g * "dog"
A star marks a node where a word ends. "car" is a word and also a prefix of "card" and "care", which is why the end marker is needed: the path alone cannot tell you whether "ca" was inserted.
How it works
Each node holds a map from character to child node plus an end-of-word flag. In our code the flag is a special key "$" inside the same map, which keeps the node a single dictionary.
-
Insert: walk down the word, creating missing children, then mark the last node as a word end. O(L).
-
Contains: walk down; fail if any character is missing; succeed only if the final node is marked. O(L).
-
Starts with: same walk, but success needs only that the walk finished. O(L).
-
Autocomplete: walk to the prefix node, then run a depth-first search below it to collect every marked node. Cost is O(L) plus the size of the subtree you enumerate. Visiting children in sorted order returns suggestions alphabetically.
Inserting cat. Green is the current node, amber nodes end a word. The first two letters follow existing edges, and only the missing letter creates a node.
Searching a trie. Prefix check and exact lookup use the same walk. They differ only in the last test: did the walk finish, versus does the final node carry the end mark.
Children representation. A map per node (dict, Map) is flexible and memory-proportional to what you store. A fixed array of 26 slots gives O(1) child access for lowercase English but wastes space when nodes are sparse. A compressed trie (radix tree) merges chains of single-child nodes into one edge labeled with a substring, trading simplicity for memory.
Trade-offs. A trie can use much more memory than a hash set, since every node carries its own map. It shines when you need prefix queries, sorted enumeration, or longest-prefix matching (as in routing). For plain membership tests, a hash set is simpler and smaller.
| Operation | Time | Notes |
|---|---|---|
| Insert word of length L | O(L) | Independent of word count |
| Exact lookup | O(L) | Needs the end marker |
| Prefix check | O(L) | Hash tables cannot do this |
| List all words under a prefix | O(L + size of subtree) | DFS below the prefix node |
| Space | O(total characters) | Worst case; shared prefixes save space |
Code: insert, lookup, autocomplete
import json
def show(*xs):
print(*(json.dumps(x, separators=(',', ':')) for x in xs))
class Trie:
def __init__(self):
self.root = {} # each node: dict of char -> child; "$" marks end of word
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True
def _walk(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return None
node = node[ch]
return node
def contains(self, word):
node = self._walk(word)
return node is not None and "$" in node
def starts_with(self, prefix):
return self._walk(prefix) is not None
def autocomplete(self, prefix):
node = self._walk(prefix)
out = []
def dfs(n, path):
if "$" in n:
out.append(prefix + path)
for ch in sorted(k for k in n if k != "$"):
dfs(n[ch], path + ch)
if node is not None:
dfs(node, "")
return out
t = Trie()
for w in ["car", "card", "care", "cat", "dog"]:
t.insert(w)
show(t.contains("car"), t.contains("ca"), t.starts_with("ca"), t.starts_with("cb"))
show(t.autocomplete("car"))
show(t.autocomplete("x"))const show = (...xs) => console.log(xs.map((x) => JSON.stringify(x)).join(" "));
class Trie {
constructor() {
this.root = new Map(); // each node: Map of char -> child; "$" marks end of word
}
insert(word) {
let node = this.root;
for (const ch of word) {
if (!node.has(ch)) node.set(ch, new Map());
node = node.get(ch);
}
node.set("$", true);
}
#walk(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node.has(ch)) return null;
node = node.get(ch);
}
return node;
}
contains(word) {
const node = this.#walk(word);
return node !== null && node.has("$");
}
startsWith(prefix) {
return this.#walk(prefix) !== null;
}
autocomplete(prefix) {
const node = this.#walk(prefix);
const out = [];
const dfs = (n, path) => {
if (n.has("$")) out.push(prefix + path);
for (const ch of [...n.keys()].filter((k) => k !== "$").sort()) {
dfs(n.get(ch), path + ch);
}
};
if (node !== null) dfs(node, "");
return out;
}
}
const t = new Trie();
for (const w of ["car", "card", "care", "cat", "dog"]) t.insert(w);
show(t.contains("car"), t.contains("ca"), t.startsWith("ca"), t.startsWith("cb"));
show(t.autocomplete("car"));
show(t.autocomplete("x"));Both versions print:
true false true false
["car","card","care"]
[]
The first line shows that "car" is a stored word, "ca" is not a word but is a valid prefix, and "cb" is not a prefix. The second line is the autocomplete for "car" (the word itself plus its extensions), and the third shows an unknown prefix returns an empty list.
Common pitfalls
- Treating a prefix as a word:
containsmust check the end marker;starts_withmust not. - Colliding the marker with real characters: if your alphabet can include the marker (for example the dollar sign), use a separate boolean field on a node object instead.
- Memory blow-up: a node object with a 26-slot array per character is heavy for large dictionaries. Prefer maps, or compress the trie.
- Recursion depth: very long words recurse deeply in the DFS. Use an explicit stack if words can be thousands of characters.
- Case and Unicode: normalize case first. For non-ASCII text, decide whether nodes are code points, bytes, or grapheme clusters.
Practice
Implement a trie with insert, search, starts-with easy
Hint
Share one helper that walks a string and returns the node it ends on, or nothing.
Show solution
Write a walk(s) helper that returns the final node or null. search is walk(word) is not null and has the end marker; startsWith is just walk(prefix) is not null. Each is O(L).
Longest common prefix of many strings medium
Hint
Insert everything, then walk from the root while the path does not branch.
Show solution
Insert all strings. From the root, repeatedly move to the only child as long as the current node has exactly one child and is not a word end. The characters you collect are the longest common prefix. O(total characters). (Comparing against the first string character by character is just as good and uses no extra memory.)
Word search II hard
Hint
Searching a grid word by word repeats work. Search for all words at once.
Show solution
Insert all target words into a trie. Run a DFS from each grid cell, moving through the trie in step with the grid path, and stop a branch the moment the current path is not a trie prefix. When you reach a word-end node, record the word (and clear the mark to avoid duplicates). The trie prunes dead branches that a per-word search would explore repeatedly.
Count words with a given prefix medium
Hint
Store a small counter in each node as you insert.
Show solution
Add a pass_count to each node that increments every time an insert passes through it. After walking to the prefix node, its pass_count is the answer in O(L), with no subtree enumeration.
Interview questions
- Why use a trie instead of a hash set of words? Prefix queries, sorted enumeration, and longest-prefix matching without scanning every word.
- What does lookup cost? O(L) for a word of length L, regardless of how many words are stored.
- What is the downside? Memory: each node has its own child container, so tries can be much larger than a hash set unless compressed.
- What is a radix tree? A compressed trie where single-child chains are merged into one multi-character edge.
- How would you rank autocomplete suggestions? Store a frequency at each word-end node and collect the top k (a heap helps) under the prefix.
Interviewers look for: recognizing prefix-search problems quickly, using the end-of-word marker correctly, and discussing memory trade-offs versus a hash set.
Quick check
A trie holds 500,000 words. How many node steps does it take to check whether the 5-letter word 'apple' is stored?
Finished this lesson?
Further resources
- Trie (Wikipedia) (article)
- MDN: Map (docs)