Tries
Think of it like this
Imagine a dictionary organized as a branching path. Instead of one entry per word, you share common prefixes. "cat", "car", "card", and "care" all start with "c-a", so you only store that path once.
Words: cat, car, card, care, bat, ball
root
/ \
c b
| |
a a
/ \ / \
t r t l
| |
d l
↑ ↑
"card" "ball"Every path from root to a marked node is a word. Shared prefixes cost nothing extra. This makes prefix queries, "show me all words starting with 'ca'", extremely fast.
Why Not Just Use a Hash Map?
A hash map gives O(1) exact lookup but has no concept of prefix relationships. With a hash map you'd need to scan ALL words to find those starting with "ca". With a trie, you walk the "c" → "a" path and then enumerate everything below, only what's relevant.
| Operation | Hash Map | Trie |
|---|---|---|
| Exact lookup | O(1) | O(L) |
| Prefix search | O(n × L), scan all | O(L + k), walk prefix, enumerate k matches |
| Autocomplete | O(n × L) | O(L + k) |
| Longest prefix match | O(n × L) | O(L) |
Prefix Traversal & Autocomplete Engine
Insert words and search prefixes to visualize $O(L)$ character path matching.
Node Structure and Implementation
class TrieNode {
constructor() {
this.children = {}; // char → TrieNode
this.isEnd = false; // true if a word ends here
this.count = 0; // optional: how many words pass through this node
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// Insert a word, O(L)
insert(word) {
let node = this.root;
for (const ch of word) {
if
Time and Space Complexity
| Operation | Complexity |
|---|---|
| Insert | O(L) where L = word length |
| Search (exact) | O(L) |
| Prefix search | O(L) |
| Autocomplete (get all) | O(L + k) where k = number of matches |
| Delete | O(L) |
Space: O(n × L × Σ) where n = words, L = avg length, Σ = alphabet size (26 for lowercase English)
Key insight: Lookup time is O(L), independent of how many words are stored. A dictionary with 1 million words has the same lookup speed as one with 100 words.