Trie (Prefix Tree)
Medium+90 XPA tree of letters where words that start the same share the same path — the magic behind autocomplete.
No visualization loaded.
Watch
—
Press Run to begin.
A trie (say 'try', short for reTRIEval) is a tree built out of letters. Every step you take down the tree adds one letter, so the path from the root to a node spells a prefix. To store a whole word you walk its letters down, making new nodes only where they don't exist yet, and mark the final node as 'end of a word.' The lovely part: words that begin the same way SHARE the same nodes — 'cat' and 'car' both walk c → a, then split — so the trie remembers each shared beginning only once.
▸What is a trie, really?
A tree where letters live on the path, not in one big lump. Start at an empty root. Each child is one letter further along. Follow a path and you spell a prefix; if the node you land on is flagged 'end-of-word,' that prefix is a real stored word. So 'storing words' becomes 'carving letter-paths into a tree.'
▸Why do words share prefixes?
Because a shared start is the SAME path. 'cat' and 'car' both begin c-a, so they reuse the exact same c node and a node, then branch to t and r. The trie never writes 'ca' twice — common beginnings are stored once. That's why a dictionary with thousands of words starting 'pre…' barely costs extra: they all share that one 'pre' path.
▸When should I use a trie instead of a hash set?
A hash set is great for 'is this EXACT word in here?' — but it can't answer 'which words START with pre…?' because hashing scrambles order and throws away the shared beginnings. A trie keeps prefixes as real paths, so prefix questions (autocomplete, 'all words under this branch') are easy. Use a hash set for exact membership; reach for a trie when prefixes matter.
▸What is a trie good for?
Anything prefix-shaped: autocomplete and search suggestions ('type pre, here are all words under the pre branch'), spell-checkers, IP routing tables, and matching many words in a text at once. The win is walking down by letter — each lookup costs only the length of the word, no matter how many words are stored.
▸How fast is it?
Insert or look up a word of length L by walking L steps down — O(L), and it does NOT slow down as you add more words, because you only ever follow one word's worth of letters. The cost is set by the word's length, not the size of the dictionary.
How the work grows
O(L) per word (L = word length) is fair — grows in step with the data. Inserting or finding a word just walks down one letter at a time, so the work is the word's LENGTH, not how many words are stored — adding more words never slows a lookup. Space is the number of nodes, which is the total letters across all words minus everything shared prefixes let you store only once.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.