Introduction to Tries (Prefix Trees)
Learn about the Trie data structure, optimized for prefix-based searching.
What is a Trie?
A Trie (pronounced "try") or Prefix Tree is a tree-based data structure used to efficiently store and retrieve keys in a dataset of strings.
It is the backbone of features like Autocomplete, Spell Check, and IP Routing.
The Motivation: Autocomplete
Imagine you have 1 million words. You type "ap". You want to find all words starting with "ap".
appleapplicationaptitude
Attempt 1: List Scan
If you store words in a list/array, you must scan every single word to check if it starts with "ap".
If you have N words of length L, checking all takes O(N * L). This is too slow for Google Search!
Visualizing Linear Search Inefficiency
Switch the figure further down to List scan to watch this: it checks 'bat' and 'cat' even though they share nothing with 'ap'.
When to use a Trie?
Pattern Recognition Triggers:
- Prefix Search: "Find all words starting with..."
- Dictionary Ops: Spell checking, validity checking.
- Bitwise XOR: Tries are surprisingly good for finding max XOR pairs.
The Intuition: Shared Prefixes
Instead of storing each string independently, let's share the storage for common prefixes.
apple,apply,aptall sharea->p.- We build a tree where each edge is a character.
- Traversing
a->ptakes us to a node representing "ap". Access isO(L), independent ofN!
Interactive Trie Walkthrough
PREFIX "ap"
LIST SCAN
Checked
0
Matches
0
Words
4
Scan the list: compare "ap" with the start of every word
Next
Compare "ap" with the start of "apple"
Words
Prefix
Legend & Complexity
List scan: the word being compared. Trie: the node being visited
List scan: a word that starts with the prefix. Trie: a node where a stored word ends
List scan: a word checked and ruled out
Trie: the path walked so far
Trie: the node with no child for the next character
List scan
O(N·L)
Trie lookup
O(L)
Trie space
O(total chars)
Compare the two methods on the same words: List scan checks every word, while Trie builds the prefix tree with insert and then answers with one startsWith walk. Checked counts the character comparisons each makes.
Dry Run: Searching 'car'
Trie contains: cat, can.
| Step | Char | Node Checks | Action |
|---|---|---|---|
| 1 | 'c' | Root has 'c' child? Yes. | Move to 'c' node. |
| 2 | 'a' | 'c' has 'a' child? Yes. | Move to 'a' node. |
| 3 | 'r' | 'a' has 'r' child? No! | Return False. |
Solution Template
The node structure with insert and startsWith, the two operations the figure runs.
Introduction to Tries (Prefix Trees) Code
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEnd = false;5 }6}78class Trie {9 constructor() {10 this.root = new TrieNode();11 }1213 insert(word) {14 let node = this.root;15 for (const char of word) {16 if (!node.children[char]) {17 node.children[char] = new TrieNode();18 }19 node = node.children[char];20 }21 node.isEnd = true;22 }2324 startsWith(prefix) {25 let node = this.root;26 for (const char of prefix) {27 if (!node.children[char]) return false;28 node = node.children[char];29 }30 return true;31 }32}
Edge Cases & Warning
Be aware of:
Empty String: Handling empty string insertion might require root to be marked isEnd.
Case Sensitivity: Usually assume lowercase 'a'-'z'. If not, Map size increases.
Memory Usage: Tries can use A LOT of memory compared to a simple list if prefixes aren't shared efficiently.
Summary
Recap: Trie trades Space (memory overhead of pointers) for Time (fast prefix lookups).