Module A-10 — Tries: Prefix Trees and Autocomplete
What this module covers: Module F-4's hash map answers "does this exact key exist" in O(1). It has no good answer at all for "what keys start with this prefix" — that requires scanning every key. A trie is a tree built specifically to make prefix queries fast, by encoding shared prefixes as shared paths through the tree. This module covers the structure, its core operations, and autocomplete — the application a trie is built for.
The Structure: Shared Prefixes Are Shared Paths
A trie (from retrieval, though commonly pronounced "try" to avoid confusion with "tree") is a tree where each edge represents one character, and any path from the root spells out a prefix. Words that share a prefix — "car", "card", "care" — literally share the same path through the tree for their common letters, only branching apart where they first differ.
typescript
"car", "card", and "care" inserted into the same trie produce a single shared path for c → a → r, with the tree only branching into three separate continuations (nothing further, d, or e) at that point — the shared prefix is stored exactly once, no matter how many words share it. isEndOfWord matters specifically because a word can be a prefix of another word ("car" is a prefix of "card") — without this flag, there'd be no way to tell whether the path to a given node represents a complete, insertable word or just an intermediate letter on the way to a longer one.
Search and StartsWith: Both Just a Walk Down the Tree
typescript
Both operations are the identical walk, differing only in the final check: search additionally requires isEndOfWord (this exact string was inserted as a complete word), while startsWith only cares that the path exists at all (some word in the trie begins this way). Both cost O(L), where L is the length of the string being searched — critically, independent of how many words the trie holds. This is the trie's core advantage over a hash map (Module F-4): a hash map's O(1) lookup only answers "does this exact key exist" — it has no efficient way at all to answer "what keys start with this prefix," short of checking every single key it holds, which is O(n × L) in the worst case. A trie answers the prefix question in the same O(L) it takes to answer the exact-match question, because the tree structure itself is organized by shared prefixes.
Autocomplete: Walk to the Prefix, Then Collect Everything Below It
Autocomplete needs "every word starting with this prefix," not just "does this prefix exist." The fix: walk to the prefix's node (exactly startsWith's walk), then run a traversal (Module P-4) from that point, collecting every complete word found in the subtree beneath it.
typescript
Walking to the prefix's node is O(L) — the length of the prefix typed so far, not the size of the whole trie. From there, collectWords is a straightforward preorder traversal (Module P-4) over just the subtree rooted at that prefix, visiting exactly the words that actually start with it — never touching any part of the trie outside that subtree, which is precisely why this stays fast even as the trie grows to hold a very large dictionary: the cost scales with how many matches exist under this specific prefix, not with the total number of words stored anywhere in the trie.
A Brief Extension: Wildcard Search
A small but common variant — supporting . as a wildcard matching any single character ("c.r" should match "car", "cur", or "cor") — requires backtracking (Module P-7) instead of a plain linear walk, since a . means "try every child at this position, not just one specific path":
typescript
A . forks the search into every available child rather than following one fixed path — the exact "try each choice, recurse, and it's fine if a given branch fails" shape from Module P-7's backtracking, applied to tree paths instead of subset/permutation generation.
Where This Shows Up in Your Stack
Search-as-you-type and autocomplete UI (the module's driving example) is precisely this structure — as a user types each additional character, the app walks one more level down the trie and re-collects the matching subtree, rather than re-filtering an entire word list from scratch on every keystroke.
IP routing tables use a trie-like structure (a binary trie over IP address bits) for longest prefix match — routing a packet to the most specific matching network range (e.g., preferring a route for 192.168.1.0/24 over a broader 192.168.0.0/16 match) is fundamentally a "how far down this trie can I walk before the path runs out" question, the same mechanic as this module's startsWith, just applied to binary address prefixes instead of letters.
Spell-checkers and dictionary lookups use a trie both to validate whether a word exists (search) and, on a miss, to suggest nearby valid words by exploring paths a small edit-distance (Module P-14) away from the typed input.
Framework route matching (resolving a URL path against a set of registered routes, some with dynamic segments) shares the same prefix-tree intuition — a request path is matched by walking down a tree of route segments, most specifically matching, rather than checking every registered route pattern independently.
Summary
A trie stores shared prefixes as shared paths, branching only where words actually differ — isEndOfWord marks which nodes represent a complete, inserted word rather than just an intermediate letter.
Insert, search, and startsWith are all O(L), where L is the length of the string involved — independent of how many total words the trie holds.
This is the trie's core advantage over a hash map: exact-match lookup is O(1) in both, but a hash map has no efficient way to answer "what starts with this prefix," while a trie answers it in the same O(L) as an exact match.
Autocomplete walks to the prefix's node (O(L)), then traverses just that subtree (Module P-4's preorder shape) to collect matching words — cost scales with matches under that prefix, not the whole trie's size.
Wildcard search generalizes the walk into backtracking (Module P-7): a wildcard character forks the search into every child instead of following one fixed path.
The next module, String Matching: Rabin-Karp and KMP, covers a related but distinct problem — finding a specific pattern inside a larger text, rather than organizing a whole dictionary of words for prefix lookups.
Knowledge Check
Why can a hash map answer "does this exact key exist" in O(1), but has no efficient way to answer "what keys start with this prefix," while a trie answers both in O(L)?
In the Trie class, what specific problem would arise if isEndOfWord were removed and search(word) simply checked whether walk(word) returned a non-null node?
Why does autocomplete's overall cost scale with "the length of the prefix, plus the number of matching words found," rather than with the total number of words stored anywhere in the trie?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
classTrieNode{ children: Map<string, TrieNode>=newMap();// char -> next node (Module F-4) isEndOfWord:boolean=false;// marks "a complete word ends exactly here"}classTrie{private root =newTrieNode();insert(word:string):void{let node =this.root;for(const char of word){if(!node.children.has(char)){ node.children.set(char,newTrieNode());} node = node.children.get(char)!;} node.isEndOfWord =true;// mark the END of this specific word, not every node visited}}
classTrie{// ...(insert above)search(word:string):boolean{const node =this.walk(word);return node !==null&& node.isEndOfWord;// must exist AND be a complete word, not just a prefix}startsWith(prefix:string):boolean{returnthis.walk(prefix)!==null;// just needs to exist as a path — doesn't need isEndOfWord}privatewalk(str:string): TrieNode |null{let node =this.root;for(const char of str){if(!node.children.has(char))returnnull;// this path doesn't exist in the trie at all node = node.children.get(char)!;}return node;}}
functionautocomplete(trie: Trie, prefix:string):string[]{const prefixNode =(trie asany).walk(prefix);// conceptually: reuse the same walk from startsWithif(prefixNode ===null)return[];const results:string[]=[];functioncollectWords(node: TrieNode, currentWord:string):void{if(node.isEndOfWord) results.push(currentWord);for(const[char, child]of node.children){collectWords(child, currentWord + char);// Module P-4's preorder shape: visit, then recurse into children}}collectWords(prefixNode, prefix);return results;}// trie contains: "car", "card", "care", "cart", "dog"autocomplete(trie,"car");// ["car", "card", "care", "cart"]
functionsearchWithWildcard(root: TrieNode, word:string):boolean{functiondfs(node: TrieNode, index:number):boolean{if(index === word.length)return node.isEndOfWord;const char = word[index];if(char ==='.'){for(const child of node.children.values()){if(dfs(child, index +1))returntrue;// try every possible branch — Module P-7's backtracking shape}returnfalse;}if(!node.children.has(char))returnfalse;returndfs(node.children.get(char)!, index +1);}returndfs(root,0);}