· 9 min deep-divedata-structuresalgorithms
Article 1 in your session
Tries — Prefix Trees for Autocomplete, Spell Check, and IP Routing
A scroll-driven visual deep dive into trie data structures. From basic prefix trees to compressed tries and radix trees — with real-world applications in autocomplete, spell checking, IP routing tables, and T9 keyboard input.
Introduction
🎯 0/3 0%
🔡
Type one letter.
Get a thousand suggestions.
How does Google Autocomplete return suggestions in under 100ms across billions of queries? How does your phone keyboard predict the next word? The answer is a trie (pronounced “try”) — a tree where each path from root to node spells out a word prefix. Search for any prefix in O(k) time where k is the prefix length, independent of the dictionary size.
↓ Scroll to build the data structure behind every search bar
Trie Structure
A Tree of Characters
Operations
Trie Operations: Insert, Search, Prefix Search
Time complexity — independent of dictionary size
Insert
Walk from the root, creating child nodes for each character as needed, then mark the final node as a word end (★). The cost depends only on the word length — adding to a 10-word trie and a 10-million-word trie takes the same time.
O(k) — k = word length Exact Search
Follow edges character by character from root. If the full path exists AND the last node is marked as a word end, the word is found. If any character is missing, the word doesn't exist — no further searching needed.
O(k) — k = word length Prefix Search (Autocomplete)
Walk k edges to reach the prefix node, then collect all complete words below it via DFS or BFS. Typing 'ap' instantly finds 'app', 'apple', 'apt' — the trie structure naturally groups words by prefix.
O(k + p) — k to reach prefix, p to collect results Delete
Walk to the word's end and unmark it as a word end. Then backtrack toward the root, removing any nodes that no longer have children or word-end markers — cleaning up unused branches.
O(k) — k = word length Key Insight
Every operation is O(k) where k is the word length, completely independent of n (the number of words stored). A trie with 1 million words searches exactly as fast as one with 10 words — only the query length matters.
↑ Answer the question above to continue ↑
🟢 Quick Check Knowledge Check
You have a trie containing 10 million English words. You search for the word 'algorithm' (9 characters). How many nodes do you visit?
💡 How many characters does the word have?
This is the trie's superpower: search time is O(k) where k is the word length, completely independent of the number of words stored. With 10 million words or 10 words, searching for 'algorithm' visits exactly 9 nodes (plus root). Compare this to a hash table (O(k) for hashing + possible collision resolution) or a sorted array (O(k × log n) for binary search with string comparisons). For prefix search, tries are uniquely efficient — no other data structure can enumerate all words with a given prefix as quickly.
Compressed Tries
Space Optimization: Compressed Tries and Radix Trees
↑ Answer the question above to continue ↑
🟡 Checkpoint Knowledge Check
You're building autocomplete for a search engine with 2 billion queries stored. A user types 'how t'. How should you design the system?
💡 Which data structure is specifically designed for prefix-based lookups?
This is essentially how Google Autocomplete works. The trie stores all queries with frequency counts. For 'how t', you walk 5 nodes to reach the 't' node under 'how '. Then DFS collects all complete queries below, ranked by frequency. Shared prefixes compress beautifully: 'how to cook', 'how to code', 'how to change' all share the 'how to c' path (8 nodes for 3 queries). A sorted array would need O(log n × k) per query with binary search. A hash table can't do prefix matching at all. SQL LIKE '%...' is a full table scan — O(n).
Real-World Uses
Tries in Production Systems
↑ Answer the question above to continue ↑
🔴 Challenge Knowledge Check
A standard trie storing 10 million English words wastes massive memory because most internal nodes have only 1 child. What optimization reduces space by 80%+ while preserving O(k) lookup?
💡 Most nodes in an English word trie have exactly one child — can you merge them?
A Patricia trie (radix tree) compresses chains of single-child nodes. Instead of 5 nodes for 'hello', store one node with the string 'hello'. For English words, ~70% of nodes are single-child chains, so compression eliminates most nodes. Lookup remains O(k) — compare substrings instead of single characters. Linux kernel routing tables, Redis, and most production autocomplete systems use this. Hash-map nodes help with sparse branching but don't address chain compression.
🎓 What You Now Know
✓ Tries store strings as paths in a tree — each edge is a character, each node represents a prefix. Search time depends on word length, not dictionary size.
✓ Prefix search is uniquely efficient in tries: O(k + p) — k to reach the prefix node, p to enumerate results. Hash maps cannot do this.
✓ Compressed tries reduce memory by merging single-child chains — turning O(total characters) space to O(unique prefixes) space.
✓ Tries power autocomplete, IP routing, spell checking, and predictive text — every search bar and every internet router uses one.
Tries are a specialized form of trees. For general hierarchical data, check out the Trees article. For hash-based lookups without prefix support, see Hash Tables. ⚡
↗ Keep Learning
deep-divedata-structuresalgorithms
Trees — Hierarchies, Traversals, and Balanced Search
A scroll-driven visual deep dive into tree data structures. Binary trees, BSTs, AVL trees, heaps, and B-trees — with real-world applications in databases, file systems, priority queues, and decision engines.
12 min
Read →
deep-divedata-structuresalgorithms
Hash Tables — O(1) Access That Powers Everything
A scroll-driven visual deep dive into hash tables. From hash functions to collision resolution (chaining vs open addressing) to load factors — understand the data structure behind caches, databases, and deduplication.
10 min
Read →
deep-divedata-structuresalgorithms
String Manipulation — Patterns, Hashing, and Sliding Windows
A scroll-driven visual deep dive into string algorithms. From brute-force pattern matching to KMP, Rabin-Karp hashing, and sliding window techniques — with real-world applications in search engines, DNA analysis, and parsers.
7 min
Read →
Comments
No comments yet. Be the first!