Word ladder games start with “CAT”, change one letter to get “COT”, then “DOT”, then “DOG”. Now imagine all possible words connected in a web where shared prefixes create natural pathways. That’s a trie: a tree structure where each path from root to leaf spells a word, with common prefixes sharing paths.
The Dictionary Dilemma
Sorted arrays support binary search in O(log n) but prefix operations require scanning. “Find all words starting with CAR” scans everything matching the prefix.
Hash tables provide O(1) lookups but lose prefix relationships. “CAR” and “CARD” share no connection in a hash table. Prefix queries scan every entry.
Enter the Word Ladder Tree
Tries organize words by prefix. The root represents empty string. Each node has one parent and multiple children, one for each possible next character.
Building the Trie
Adding “CAT”: from root, create ‘C’ child, from ‘C’ create ‘A’ child, from ‘A’ create ‘T’ child, mark ‘T’ as word ending.
Adding “CAR”: from root, follow existing ‘C’, follow existing ‘A’, from ‘A’ create ‘R’ child, mark ‘R’ as word ending.
The ladder branches where words diverge.
This diagram requires JavaScript.
Enable JavaScript in your browser to use this feature.
Words in the trie: CAT, CAR, CARD, CARE, CAREFUL (* marks word endings)
The Prefix Property
All words with prefix “CAR” live in the CAR subtree. Finding them requires traversing that subtree. Adding “CARING” extends from existing “CARE”. Common prefixes share storage.
Real-World Applications
Autocomplete
User types “HEL”. Navigate to H-E-L node, traverse subtree, collect all words below. Results: HELLO, HELP, HELPFUL, HELICOPTER. One traversal finds all suggestions.
Spell Checker
To check if “HELLLO” (extra L) exists: follow H-E-L-L, try to follow second L, no child exists, not a valid word. From H-E-L-L, find children that lead to valid words, suggest “HELLO”.
IP Router Tables
Route table contains: 192.168.* -> Router A, 192.168.1.* -> Router B, 10.* -> Router C. Lookup 192.168.1.5: follow 192 to 168 to 1, most specific match (192.168.1.*) wins. Longest prefix match via trie traversal.
Operations
Insertion
Adding “CARDS”: follow C -> A -> R -> D, D is already marked as word (CARD exists), add child ‘S’ to D, mark S as word ending. Entire CARD prefix reused.
Deletion
Removing “CAR”: navigate to C -> A -> R, unmark R as word ending, R has children (D, E) so keep the node. CAR removed, CARD and CARE preserved.
Search
Finding words with prefix “CA”: navigate to C -> A, DFS from A node, collect paths to word endings. One traversal finds all matches.
Longest Common Prefix
Words: CARBON, CARROT, CARPET. All share C -> A -> R, then diverge. Longest common prefix is “CAR”. Follow path while all words agree, stop at divergence.
Common Challenges
Memory Overhead
Each node stores character, array of 26 child pointers (for English), word ending flag, optional parent pointer. Sparse tries waste space on null pointers. Chains of single-child nodes consume memory inefficiently.
Solutions: compressed tries (radix trees), hash maps for children, array of pairs instead of fixed array.
Unicode
English alphabet: 26 children per node maximum. Unicode: potentially millions of possible next characters. Cannot pre-allocate. Use hash maps, ternary search trees, or byte-level encoding.
Deletion Complexity
Removing “CARE” when “CAREFUL” exists: cannot delete the shared C-A-R-E path because CAREFUL still needs it. Delete leaf upward, stop at first word ending or first branching point.
Persistence
Saving tries to disk: pointer-based structure cannot serialize directly. Use level-order serialization, depth-first with markers, or succinct representations.
Variants
Compressed Tries (Radix Trees)
Merge chains of single-child nodes. “SLOW” and “SLOWLY” become “SLOW” -> “LY” edge instead of S -> L -> O -> W -> L -> Y. Path compression saves space.
Suffix Trees
Store all suffixes of a word. “BANANA” has suffixes BANANA, ANANA, NANA, ANA, NA, A. Enables substring search and pattern matching in O(n) where n is text length.
Ternary Search Trees
Three-way branching: less than, equal to, greater than current character. More space-efficient for sparse alphabets, trades time for space.
Concurrent Tries
Lock-free traversal, copy-on-write updates, versioned nodes. Enable parallel access from multiple threads without locking readers.
When Tries Apply
Tries work when:
- Prefix operations dominate your workload
- Autocomplete or spell-checking is needed
- IP routing or pattern matching is the domain
- Memory is available for the overhead
Hash tables win when:
- Exact match is the only operation
- Memory is constrained
- Keys have no structural relationship
Decision Rules
Use a trie when:
- Prefix queries are frequent
- You need autocomplete or suggestions
- Memory overhead is acceptable
- Alphabet size is manageable (or compression is used)
Use a hash table when:
- Only exact lookups matter
- Memory is tight
- Keys have no common prefixes
The ladder stands ready. Each rung a letter, each path a word. Climb from root to meaning.
