Every keystroke in a search box that triggers a fresh list of suggestions is really asking one specific question, fast, over and over: give me every word you know that starts with what I've typed so far. A hash table can answer "do you have this exact string" in O(1) — but it has no concept of a partial match at all; the only way to find every stored word starting with "ca" is to check every single word you have. A trie is the data structure built specifically to answer the prefix question directly, without scanning anything.
One node per character, not per word
A trie's core trick is structural: instead of storing each word as its own unit, it stores one node per character, and words that share a prefix literally share the same nodes for that prefix. Insert cat, car, card, care, do, dog, and dot, and the shared beginnings — ca and do — each collapse into a single path instead of being duplicated seven times:
the dot marks isEndOfWord — every other node is only ever a step along the way
Every node holds a character, a map of child nodes (one per possible next character — not capped at two the way a binary tree's are), and one boolean: isEndOfWord.
The gotcha: a path existing isn't the same as a word being stored
This is the detail that trips people up the first time they implement one. After inserting card and care but never inserting the plain word car on its own, the path c → a → r absolutely exists in the trie — you can walk it character by character without hitting a dead end. But that node for r was never marked isEndOfWord, so searching for "car" correctly reports it as not found, distinct from a path that doesn't exist at all. A trie search has to check both things — did the path resolve, and is this specific node actually flagged as a complete word — because a prefix of something longer and a word are two different states the same node can be in.
Autocomplete is just one operation: walk, then collect
This is the payoff for the whole structure. Given a typed prefix, autocomplete does exactly two steps: walk down the trie one character at a time following the prefix, then, from whatever node that lands on, collect every isEndOfWord node in the subtree below it. Reach the node for "ca" in the trie above and collecting below it finds cat, car, card, and care — every word starting with that prefix, found by touching only the nodes that are actually relevant, never the unrelated do/dog/dot branch at all.
Deleting has to check before it removes anything
Deleting car can't just unmark that node and walk away — card and care still depend on that exact same path existing. The correct delete unmarks isEndOfWord first, then walks back up toward the root pruning nodes — but only a node with zero children that isn't itself the end of some other word. Delete dot from the trie above and the node for t gets pruned (it has no children and marks no other word), but the walk back up stops the instant it reaches o — that node is still isEndOfWord for do, and still has g hanging off it for dog, so it survives.
Why not just use a hash table or a BST?
A trie's insert, search, and delete all run in O(L) time, where L is the length of the word being processed — not O(log n) the way a balanced tree scales with the number of stored items, and not the O(1) average case of a hash table. On raw exact-match lookup speed, a hash table usually wins. The reason to reach for a trie instead is never raw lookup speed — it's that a hash table has no way to answer a prefix query without checking every key it holds, and a BST's ordering only helps with range queries over the whole keyspace, not the specific "everything starting with X" question. A trie answers that question by construction, because prefixes are literally what its structure is organized around.
Where this shows up outside a search box
- Spell-checkers use the same "path exists but isn't a word" check to distinguish a typo from a valid word that just happens to be a prefix of another one.
- IP routing tables use a bit-level trie to find the longest matching prefix for a destination address — the exact same walk-then- check-further pattern, just with binary digits as the "characters."
- T9 and predictive text on older phone keypads used a trie to narrow down candidate words as each ambiguous digit was pressed, one node deeper per keypress.
Try it yourself
Trie Visualizer runs insert, search, delete, and the prefix-collecting startsWith operation on a real trie, step by step — watch the isEndOfWord flag get set and cleared, and watch a delete stop pruning the instant it hits a node still needed by another word. For the other structures mentioned here, see Hash Table Explained and Understanding B-Trees. All tools run entirely in your browser.