I spent an embarrassing amount of time last week reimplementing something I'd "known" since a data structures class a decade ago: the trie. Typing it out from scratch again reminded me why it's one of the few data structures that actually earns the "elegant" label people throw around too easily.
Here's the pitch in one sentence: a trie stores strings by character, along shared paths from a root, so two words with the same prefix walk the exact same nodes until they stop agreeing. Insert "car," "card," and "care," and you get one shared path for "c-a-r," which then splits into three different endings. Nothing about adding "care" touches the nodes "car" and "card" already built.
That sharing is the whole point, and it's easy to undersell how much it buys you. A hash set can tell you "yes, this exact string is in the collection." That's it. It cannot tell you "give me everything that starts with these three letters" without scanning the entire set and checking each entry one by one. A trie answers that second question by walking to the end of the prefix and then just... looking at what's underneath. Lookup cost depends on how long your prefix is, not on how many million other strings happen to be sitting next to it in memory. That's the entire mechanism behind every autocomplete dropdown you've ever typed into: walk the prefix, then collect every real word hanging off wherever you land.
The part that actually bit me while rebuilding this: you need an explicit marker for "a real word ends here." It sounds obvious written down, but it's the single easiest thing to forget, and the bug it causes is sneaky. Say you only ever insert "card." The path c → a → r → d exists in your trie. All four nodes are real. But "car" was never inserted as its own entry, it's just a prefix that happens to lead somewhere. If your node doesn't carry a boolean flag for "an insertion actually terminated here," you have no way to distinguish a real stored word from a string that merely happens to be a prefix of a longer one. I've seen (and once written) autocomplete bugs where a partial prefix gets suggested as a complete match because of exactly this missing flag.
The tradeoff nobody mentions in the five-minute version of this concept: a naive implementation wastes a lot of memory. The textbook approach gives every node a fixed-size array, one slot per possible next character. Twenty-six slots if you're doing lowercase English, more if you need digits or punctuation or, god forbid, full Unicode. Most of those slots sit empty on any node that doesn't branch in every direction, and that waste adds up fast across a trie with real-world vocabulary in it. The fix is one of two things: back each node with a hash map instead of a fixed array, so you only pay for children that actually exist, or compress the whole structure with something like a radix trie, which collapses long runs of single-child nodes into one node holding a whole substring instead of one character. "Cardboard" doesn't need five separate one-character hops after "card," it needs one node labeled "board."
Autocomplete is the use case everyone reaches for first, and it's a good one, but it's not the only place this shows up. Spell-checkers use the same walk to confirm a word exists in a dictionary and to find near-miss suggestions by exploring nearby paths. IP routers use a binary version of the same idea, walking a trie over address bits instead of letters, to do longest-prefix-match routing: find the most specific rule that matches a destination address. Different alphabet, same shared-prefix-sharing-a-path trick underneath.
I ended up writing both a longer explanation and a small interactive visualizer, mostly because I wanted to actually watch the branching happen rather than just trust my own mental model of it. If you want to poke at it yourself, the guide walks through the insert/search mechanics and the end-of-word gotcha in more detail, and the visualizer lets you insert your own words and watch the prefix lookup highlight in real time, suggestions and all.
If you've never implemented one, it's a genuinely good weekend exercise. Small enough to build in an hour. Annoying enough, in the best way, that you'll start second-guessing every search box you touch afterward.
Top comments (0)