What Is a Trie? Structure & Intuition
Character-by-Character Navigation
Read aloud is unavailable in this browser.
One Character at a Time
Imagine reading a word one letter at a time, where each letter tells you exactly which path to follow. That's precisely how you navigate a trie.
Unlike a binary search tree where you compare the entire key at each node, a trie consumes one character per level. The character you're looking at determines which child to visit. There's no comparison in the traditional sense—just direct indexing.
This character-by-character navigation is the heartbeat of all trie operations. Understanding it deeply means understanding tries completely.
By the end of this page, you will understand exactly how navigation works in a trie—how each character maps to an edge, how the process resembles following a recipe, and why this approach yields O(m) time complexity where m is the length of the string being processed. You'll see navigation as the primitive from which all trie operations are built.
The Navigation Mental Model
Let's establish a clear mental model for how navigation works:
The Pointer and String Model:
- You have a pointer to the current node (initially the root)
- You have a string to process (e.g., "search")
- You have an index into the string (initially 0)
The Navigation Loop:
while index < string.length:
char = string[index]
if current_node has child for char:
current_node = that child
index += 1
else:
FAIL: string not found / prefix doesn't exist
SUCCESS: current_node is where the string leads
That's it. Every trie operation is a variation on this loop.
In a BST, you compare keys: 'is this key less than or greater than the node's key?' In a trie, you don't compare—you index. The character 'c' means 'go to child[c]'. There's no branching decision; the character IS the decision. This is why tries are sometimes called 'digital trees'—each character is like a digit that directly addresses the next level.
Why direct indexing is powerful:
With an array-based node structure (children[26] for lowercase letters), finding the child for character 'c' is O(1):
child_index = char - 'a' // 'c' - 'a' = 2
next_node = current_node.children[child_index]
No loops, no comparisons, no searching. The character maps directly to an array slot. This is as fast as indexing gets.
Tracing Navigation: A Detailed Walkthrough
Let's trace navigation for different strings through a trie containing: {car, card, care, careful, cat}.
The trie structure (recall from previous page):
[root]
|
c
|
a
/
r* t*
/
d* e*
|
f
|
u
|
l*
Searching for 'car':
| Step | Current Node | Remaining String | Action |
|---|---|---|---|
| 0 | root | "car" | Look for child 'c' |
| 1 | c-node | "ar" | Found 'c' child, move. Look for 'a' |
| 2 | a-node | "r" | Found 'a' child, move. Look for 'r' |
| 3 | r-node | "" | Found 'r' child, move. String exhausted |
String exhausted. Check: Is r-node marked as end-of-word? Answer: Yes! (marked with *) Result: "car" EXISTS in trie ✓
Navigation Outcomes: Success and Failure Modes
Navigation can end in several distinct ways, and understanding these modes is crucial for implementing trie operations correctly:
- •Complete path, is end-of-word: String exhausted at a node marked end-of-word. The string exists in the trie. (e.g., searching "car" when "car" is stored)
- •Complete path, NOT end-of-word: String exhausted at an unmarked node. The string is a prefix of stored words, but not itself stored. (e.g., searching "ca" when only "car" is stored)
- •Incomplete path: Navigation failed mid-string because no edge existed for the next character. The string neither exists nor has any extensions in the trie. (e.g., searching "dog" when no 'd' words exist)
How different operations interpret outcomes:
| Operation | Complete + End-of-Word | Complete + Not End-of-Word | Incomplete Path |
|---|---|---|---|
| search(word) | Return true | Return false | Return false |
| startsWith(prefix) | Return true | Return true | Return false |
| insert(word) | Already exists | Mark end-of-word | Create missing path |
| delete(word) | Remove if safe | Word doesn't exist | Word doesn't exist |
Notice how the same navigation process feeds different operations—they just interpret the outcome differently.
The difference between search() and startsWith() is minimal: • search() returns true only if navigation completes AND final node is end-of-word • startsWith() returns true if navigation completes, regardless of end-of-word status
Both use identical navigation logic—they differ only in the final check.
Time Complexity: Why O(m) is Powerful
The time complexity of trie navigation is O(m), where m is the length of the string being processed. This deserves careful analysis because it's fundamentally different from other data structures.
The O(m) breakdown:
- Loop iterations: Exactly m (one per character)
- Per-iteration work: O(1) with array-based children
- Child lookup: O(1) array index
- Pointer update: O(1)
- Index increment: O(1)
- Total: O(m × 1) = O(m)
What's remarkable: no log n term.
In a balanced BST storing n strings:
- Search: O(m × log n) — because you traverse O(log n) nodes, comparing O(m) characters at each
- Even hash tables: O(m) for hashing + O(1) lookup = O(m), but hashing touches every character anyway
The trie matches hash table performance for exact lookup but also supports prefix operations that hash tables cannot.
| Data Structure | Search Complexity | For 10-char string in 1M entries |
|---|---|---|
| Unsorted Array | O(n × m) | ~10 million char comparisons |
| Sorted Array + Binary Search | O(m × log n) | ~200 char comparisons (20 comparisons × 10 chars) |
| Balanced BST | O(m × log n) | ~200 char comparisons |
| Hash Table | O(m) | ~10 operations (hashing) + O(1) lookup |
| Trie | O(m) | Exactly 10 edge traversals |
Trie search time does not depend on how many strings are stored. Whether you have 100 strings or 100 million, searching for 'algorithm' takes exactly 9 steps. This is a fundamental advantage for massive datasets with bounded string lengths.
Child Lookup: Array vs Map
The O(1) per-character claim assumes constant-time child lookup. How you implement the children structure affects both performance and memory:
- •Structure: children[26] for lowercase letters
- •Lookup: children[char - 'a'] → O(1)
- •Memory: 26 pointers per node (even if mostly null)
- •Best for: Fixed, small alphabets (a-z, DNA bases)
- •Cache behavior: Excellent—predictable memory access
- •Structure: Map<char, Node>
- •Lookup: map.get(char) → O(1) amortized
- •Memory: Only stores actual children
- •Best for: Large/variable alphabets (Unicode)
- •Cache behavior: Less predictable (hash table overhead)
Practical guidance:
if (alphabet_size <= 62 && node_density is high):
use array-based children
else if (alphabet_size > 100 or nodes are sparse):
use hash map-based children
else:
benchmark both for your specific data
For most English word applications, the 26-slot array is the right choice. The memory overhead is acceptable, and the lookup speed is unbeatable.
For Unicode text, file paths, or URLs, hash map children avoid allocating 65,536 slots per node while still providing O(1) average lookup.
For very sparse nodes with small alphabets, a sorted array of (char, child) pairs with binary search offers a middle ground: better memory than fixed arrays, better cache locality than hash maps. Lookup is O(log k) where k is the number of children (typically small). Used in some production tries.
Navigation as the Universal Building Block
Nearly every trie operation starts with the same navigation pattern. Once you master it, the operations become straightforward variations:
Core Navigation Pattern:
function navigate(root, word) {
let current = root;
for (const char of word) {
if (!current.children[char]) {
return { found: false, node: current, remaining: /* chars not processed */ };
}
current = current.children[char];
}
return { found: true, node: current, remaining: '' };
}
How operations use this pattern:
| Operation | Uses Navigate | Then Does |
|---|---|---|
| search(word) | navigate(word) | Check if node.isEndOfWord |
| startsWith(prefix) | navigate(prefix) | Return found === true |
| insert(word) | navigate(word) | Create missing nodes, mark end-of-word |
| delete(word) | navigate(word) | Unmark end-of-word, cleanup if needed |
| autocomplete(prefix) | navigate(prefix) | DFS to collect all words in subtrie |
| countPrefix(prefix) | navigate(prefix) | Count end-of-word nodes in subtrie |
The navigate function is your Swiss Army knife. Every operation is navigate + a simple post-processing step.
When building a trie, implement and test navigation thoroughly before adding operations. If navigation works correctly, the operations are trivial. If navigation is buggy, every operation will fail in subtle ways. Navigation is the foundation—get it right.
Edge Cases and Common Pitfalls
Even simple navigation has edge cases that trip up implementers. Master these to write robust trie code:
- •Empty string: What happens when you navigate with ""? You start at root and immediately finish. Is root end-of-word? Handle this case explicitly.
- •Case sensitivity: Is 'Cat' the same as 'cat'? Decide upfront and normalize input. Most tries lowercase everything during insert/search.
- •Non-alphabetic characters: What about spaces, hyphens, apostrophes in "ice-cream" or "don't"? Map them to indices or use hash map children.
- •Null children check: Always check if children[char] exists before dereferencing. Off-by-one errors in character-to-index mapping cause crashes.
- •Integer overflow in large alphabets: If char-to-index produces negative or too-large indices, you'll corrupt memory or crash.
1234567891011121314151617181920212223242526272829303132
function navigate(root: TrieNode, word: string): NavigationResult { // Handle empty string edge case if (word.length === 0) { return { found: true, node: root, index: 0 }; } let current = root; for (let i = 0; i < word.length; i++) { // Normalize: lowercase only letters const char = word[i].toLowerCase(); // Validate character is in expected range if (char < 'a' || char > 'z') { // Option 1: Skip invalid chars // Option 2: Return failure // Option 3: Use hash map children continue; // Skipping for this example } const index = char.charCodeAt(0) - 'a'.charCodeAt(0); // Check child exists before navigating if (!current.children[index]) { return { found: false, node: current, index: i }; } current = current.children[index]; } return { found: true, node: current, index: word.length };}KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.