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 → 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.
Why can a hashmap not efficiently answer "give me every word starting with this prefix"?
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.