Intermediate · Module 15 · Lesson 1
Trie / prefix tree
Character edges, terminal markers, and prefix lookup.
Lesson 83 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Trie Insert and Search
Share character prefixes across words
Phase
insert
Word
cat
Prefix
c
Result
working
Why this step happens
No 'c' edge exists here, so create node “c”.
Each root-to-node path spells exactly one stored prefix.
Trie (Prefix Tree): O(L) Dictionary Search & Autocomplete
A Trie (Prefix Tree) is a specialized k-ary tree structure designed for high-performance string storage and retrieval. Instead of storing entire strings in nodes, characters are represented by edges. Every path from root to a node represents a common prefix. Exact search, insertion, and prefix matching (startsWith) operate in O(L) time where L is string length, completely independent of dictionary size N.
Architectural Boundary · Do Not Confuse
Hash Set Lookup
Trie Prefix Lookup
Hash sets offer O(L) exact string lookup, but cannot perform prefix matching ("words starting with 'app'") without scanning all N entries (O(N × L)). Tries answer prefix queries in O(L) time.
public class Trie {
private static class Node {
Node[] children = new Node[26];
boolean isEndOfWord = false;
}
private final Node root = new Node();
public void insert(String word) {
Node curr = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) {
curr.children[idx] = new Node();
}
curr = curr.children[idx];
}
curr.isEndOfWord = true;
}
public boolean search(String word) {
Node node = getNode(word);
return node != null && node.isEndOfWord;
}
public boolean startsWith(String prefix) {
return getNode(prefix) != null;
}
private Node getNode(String str) {
Node curr = root;
for (char c : str.toCharArray()) {
int idx = c - 'a';
if (curr.children[idx] == null) return null;
curr = curr.children[idx];
}
return curr;
}
}Active Recall Checkpoint
What is the worst-case space complexity of a Trie storing N words of maximum length L over an alphabet of size Σ (e.g. 26 lowercase characters)?
Show answer & explanation
O(N × L × Σ) in the worst case where no words share prefixes. In practice, shared prefixes compress storage significantly, especially in real-world dictionaries and IP routing tables.
Use it when
Use Tries for search engine typeahead autocomplete, spell checkers, IP router Longest Prefix Match (LPM), and Boggle board word games.
Reconsider when
For small dictionaries with fixed length strings or when only exact match equality is ever queried, a standard HashSet has lower pointer memory overhead.
Cost Model
Complexity & Trade-offs
When to use it
- Autocomplete, dictionary prefixes, wildcard matching, overlap, and scheduling.
- Sharing common string prefixes.
- Reducing range problems to ordered start/end events.
Common mistakes
- Forgetting terminal markers in a trie.
- Treating touching intervals as overlap without checking the problem convention.
- Processing equal-time events in the wrong order.
Practice prompts
- Reproduce the worked Trie / prefix tree example without looking at the trace.
- Change one input condition and explain whether the Trie / prefix tree invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check