What Is a Trie? - Learning Module

Loading content...

0/276

Character-by-Character Navigation

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.\n\nUnlike 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.\n\nThis character-by-character navigation is the heartbeat of all trie operations. Understanding it deeply means understanding tries completely.

What You Will Learn

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:\n\nThe Pointer and String Model:\n\n1. You have a pointer to the current node (initially the root)\n2. You have a string to process (e.g., "search")\n3. You have an index into the string (initially 0)\n\nThe Navigation Loop:\n\n\nwhile index < string.length:\n char = string[index]\n if current_node has child for char:\n current_node = that child\n index += 1\n else:\n FAIL: string not found / prefix doesn't exist\n\nSUCCESS: current_node is where the string leads\n\n\nThat's it. Every trie operation is a variation on this loop.

Direct Indexing, Not Comparison

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:\n\nWith an array-based node structure (children[26] for lowercase letters), finding the child for character 'c' is O(1):\n\n\nchild_index = char - 'a' // 'c' - 'a' = 2\nnext_node = current_node.children[child_index]\n\n\nNo 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}.\n\nThe trie structure (recall from previous page):\n\n [root]\n |\n c\n |\n a\n / \\\n r* t*\n / \\\n d* e*\n |\n f\n |\n u\n |\n l*\n

Searching for 'car':\n\n| Step | Current Node | Remaining String | Action |\n|------|--------------|------------------|--------|\n| 0 | root | "car" | Look for child 'c' |\n| 1 | c-node | "ar" | Found 'c' child, move. Look for 'a' |\n| 2 | a-node | "r" | Found 'a' child, move. Look for 'r' |\n| 3 | r-node | "" | Found 'r' child, move. String exhausted |\n\nString exhausted. Check: Is r-node marked as end-of-word?\nAnswer: Yes! (marked with *)\nResult: "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:

Navigation Termination Scenarios

•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:\n\n| Operation | Complete + End-of-Word | Complete + Not End-of-Word | Incomplete Path |\n|-----------|------------------------|---------------------------|-----------------|\n| search(word) | Return true | Return false | Return false |\n| startsWith(prefix) | Return true | Return true | Return false |\n| insert(word) | Already exists | Mark end-of-word | Create missing path |\n| delete(word) | Remove if safe | Word doesn't exist | Word doesn't exist |\n\nNotice how the same navigation process feeds different operations—they just interpret the outcome differently.

startsWith vs search

The difference between search() and startsWith() is minimal:\n• search() returns true only if navigation completes AND final node is end-of-word\n• startsWith() returns true if navigation completes, regardless of end-of-word status\n\nBoth 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:\n\n1. Loop iterations: Exactly m (one per character)\n2. Per-iteration work: O(1) with array-based children\n - Child lookup: O(1) array index\n - Pointer update: O(1)\n - Index increment: O(1)\n3. Total: O(m × 1) = O(m)\n\nWhat's remarkable: no log n term.\n\nIn a balanced BST storing n strings:\n- Search: O(m × log n) — because you traverse O(log n) nodes, comparing O(m) characters at each\n- Even hash tables: O(m) for hashing + O(1) lookup = O(m), but hashing touches every character anyway\n\nThe trie matches hash table performance for exact lookup but also supports prefix operations that hash tables cannot.

Search Time: Trie vs Alternatives
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

The Independence Property Revisited

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:

Array-Based Children

•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

Hash Map-Based Children

•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:\n\n\nif (alphabet_size <= 62 && node_density is high):\n use array-based children\nelse if (alphabet_size > 100 or nodes are sparse):\n use hash map-based children\nelse:\n benchmark both for your specific data\n\n\nFor most English word applications, the 26-slot array is the right choice. The memory overhead is acceptable, and the lookup speed is unbeatable.\n\nFor Unicode text, file paths, or URLs, hash map children avoid allocating 65,536 slots per node while still providing O(1) average lookup.

The Third Option: Sorted Arrays

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:\n\nCore Navigation Pattern:\n\njavascript\nfunction navigate(root, word) {\n let current = root;\n for (const char of word) {\n if (!current.children[char]) {\n return { found: false, node: current, remaining: /* chars not processed */ };\n }\n current = current.children[char];\n }\n return { found: true, node: current, remaining: '' };\n}\n

How operations use this pattern:\n\n| Operation | Uses Navigate | Then Does |\n|-----------|---------------|-----------|\n| search(word) | navigate(word) | Check if node.isEndOfWord |\n| startsWith(prefix) | navigate(prefix) | Return found === true |\n| insert(word) | navigate(word) | Create missing nodes, mark end-of-word |\n| delete(word) | navigate(word) | Unmark end-of-word, cleanup if needed |\n| autocomplete(prefix) | navigate(prefix) | DFS to collect all words in subtrie |\n| countPrefix(prefix) | navigate(prefix) | Count end-of-word nodes in subtrie |\n\nThe navigate function is your Swiss Army knife. Every operation is navigate + a simple post-processing step.

Implement Navigate First

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:

Common Pitfalls

•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.

robust-navigation.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 };
}

Iterative vs Recursive Navigation

Navigation can be implemented iteratively or recursively. Both are valid, but they have different trade-offs:

navigation-styles.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// ===== ITERATIVE NAVIGATION =====
function searchIterative(root: TrieNode, word: string): boolean {
    let current = root;
    
    for (const char of word) {
        const index = char.charCodeAt(0) - 'a'.charCodeAt(0);
        if (!current.children[index]) {
            return false;
        }
        current = current.children[index];
    }
    
    return current.isEndOfWord;
}
 
// ===== RECURSIVE NAVIGATION =====
function searchRecursive(node: TrieNode, word: string, depth: number = 0): boolean {
    // Base case: processed all characters
    if (depth === word.length) {
        return node.isEndOfWord;
    }
    
    const index = word.charCodeAt(depth) - 'a'.charCodeAt(0);
    const child = node.children[index];
    
    // No path for this character
    if (!child) {
        return false;
    }
    
    // Recurse to next character
    return searchRecursive(child, word, depth + 1);
}

Iterative vs Recursive Trade-offs
Aspect	Iterative	Recursive
Readability	Linear, straightforward	Elegant for tree operations
Stack usage	O(1)	O(m) — can overflow for long strings
Performance	Slightly faster (no call overhead)	Slightly slower (function calls)
Extending to subtree ops	Need separate traversal	Natural for DFS-based operations
Debugging	Easy to inspect current state	Need to trace call stack

Practical Recommendation

Use iterative for simple search/insert operations—it's faster and won't stack overflow on long strings. Use recursive for operations that need to traverse the entire subtrie (like autocomplete or deletion), where the tree structure maps naturally to recursion.

Summary: Mastering Navigation

Character-by-character navigation is the heart of all trie operations. Let's consolidate the key insights:

Navigation Essentials

•One character = one level: Each character in the string corresponds to one step deeper into the trie.
•Direct indexing, not comparison: The character tells you exactly which child to visit—no if/else decisions.
•O(m) complexity: Navigation time depends only on string length, independent of trie size.
•Three outcomes: Complete path with end-of-word, complete path without end-of-word, or incomplete path.
•Operations differ only in interpretation: search, startsWith, insert all use the same navigation—they just do different things with the result.
•Iterative for simple ops, recursive for subtree ops: Match your implementation style to your operation's needs.

What's next:\n\nYou now understand how to navigate a trie character by character. The final page of this module brings everything together with visual representations—diagrams and mental models that make trie structure and behavior concrete and intuitive.

Page Complete

You've mastered trie navigation—the fundamental operation that all trie algorithms build upon. With navigation understood, you can implement any trie operation by simply adding the appropriate post-navigation logic. Next, we'll visualize trie structures to cement your understanding.