Tries: Prefix Trees for Autocomplete
You'll learn to
- -Explain why a hashmap cannot efficiently answer "every word starting with this prefix"
- -Implement insert, search, and starts_with on a trie
- -Recognize real-world uses of tries beyond autocomplete
A hashmap answers "is this exact word present?" in O(1). Tier 4 covered exactly why. But ask it a slightly different question, "give me every word that starts with 'app'," and it has no good answer beyond scanning every single key and checking a string prefix, which is O(n) in the number of stored words, no matter how good the hash function is. A hashmap has no concept of one key being "close to" another. Every key is an independent, unrelated bucket. A trie (pronounced "try," from re**trie**val) is a tree built specifically so that shared prefixes are shared structure, making prefix queries fast and natural instead of a brute-force scan.
The Structure: One Node Per Character
Each node in a trie represents one character position, and holds a mapping from "next character" to child node. Inserting "cat" and "car" means both words share the path C to A, then split into a T child and an R child at that point. Words that share a prefix quite literally share the nodes for that prefix. The shared structure is the entire point.
Why is_end Matters
The `is_end` flag is what separates "a valid path exists" from "a real word ends here." After inserting "app" and "apple," the path for "app" exists inside the path for "apple," but "app" itself was also inserted as a complete word, so its node needs its own marker. Without `is_end`, you could not tell the difference between "app" being a word in its own right versus merely being a prefix that happens to lead somewhere.
Notice `search` and `starts_with` share almost all their logic. Both walk character by character and fail the moment a needed child is missing. The only difference is the final check: `search` additionally requires `is_end` to be true (a complete word, not just a valid prefix), while `starts_with` is satisfied the moment the walk completes at all.
- -Autocomplete: walk to the node for the typed prefix, then explore everything beneath it to suggest completions.
- -Spell-check: a fast way to test whether a candidate word exists in a dictionary of valid words.
- -IP routing tables: routers use a trie-like structure (over bits, not characters) to find the longest matching prefix for a destination address, the same "shared prefix, shared structure" idea, just on binary strings instead of text.
Insert, search, and starts_with are all O(L) where L is the length of the word or prefix, independent of how many other words are stored in the trie. That is the trie's whole advantage over a hashmap for this exact use case: prefix queries cost the same whether you have ten words stored or ten million.
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.
Level 65: Trie from Scratch asks you to implement this Trie class, insert, search, and starts_with, as a prefix tree for autocomplete, exactly as above.