Store words by their letters, sharing every common prefix. Lookup depends on word length, not dictionary size — which is why autocomplete stays instant no matter how many words you add.
Controls
Prefix Tree
step 0
Insight
Each edge is a character; each path from the root spells a prefix. Words sharing a prefix share the same nodes — stored once.
words0
nodes1
chars if stored flat0
saved by sharing0
Complexity
Search / insertO(L)
AutocompleteO(L + results)
SpaceO(total chars)
Trie (Prefix Tree)
The structure that makes autocomplete feel instant.
Quick Context
A trie (from retrieval, usually pronounced "try") stores strings as paths through a tree. Each edge carries a character, so following a path from the root spells out a prefix. Words sharing a prefix share those nodes.
Lookup Does Not Care How Many Words You Have
Searching for a word of length L costs O(L) — one step per character. Crucially, that is independent of how many words the trie contains. A dictionary of ten words and one of ten million both answer a five-letter query in five steps.
Compare that with a balanced BST at O(L log n), where n is the dictionary size. The trie wins because it navigates by content rather than by comparison.
Prefix Queries Are the Real Superpower
A hash table can beat a trie for exact lookup — O(L) to hash versus O(L) to walk, with a smaller constant. But a hash table cannot answer "which words start with 'car'?" without scanning everything.
A trie answers it structurally: walk to the node for "car", then collect every word in the subtree beneath it. Press Autocomplete prefix and watch the subtree light up. That single property is why tries power search suggestions, IDE completion, and routing tables.
Marking Where Words End
Not every node is a word. Inserting "car" and "care" means "car" ends partway down the path to "care", so each node carries an is-word flag, drawn here as a filled circle.
Without it you could not tell whether a path spells a real word or merely a prefix of one — and searching for "ca" would wrongly succeed.
The Cost: Memory
Tries trade space for speed. A naive implementation gives every node an array of 26 child pointers, most of them null — enormously wasteful on sparse dictionaries.
Practical fixes: use a hash map of children instead of a fixed array, or switch to a radix tree (compressed trie), which merges chains of single-child nodes into one edge holding a whole substring. That is what IP routing tables use.
Watch the "saved by sharing" figure as you add words with common prefixes — sharing is what claws some of that memory back.
Interactive Exploration Guide
Load the sample words and note how car, card, care and careful all share one path for 'c-a-r'.
Insert a word starting with a new letter. A whole new branch appears from the root — nothing to share.
Search for 'car' after inserting 'card'. The path exists, but whether it is a word depends entirely on the end-of-word flag.
Autocomplete 'car'. Walk to that node, then every word beneath it is a completion — found without touching the rest of the dictionary.
Compare nodes with flat character count. The gap is exactly the memory prefix sharing saves.
Key Takeaway
A trie stores strings as paths, sharing common prefixes. Lookup is O(word length) regardless of dictionary size, and prefix queries fall out of the structure for free — which no hash table can match. The price is memory, mitigated by hash-map children or radix compression.
Cheat sheet
Trie (Prefix Tree)
Store words by their letters, sharing every common prefix. Lookup depends on word length, not dictionary size — which is why autocomplete stays instant no matter how many words you add.