Tries, One Letter at a Time

A trie is what you get when you stop storing whole words and start storing paths through the alphabet instead. Every node is one character. Every edge is 'the next letter.' A word is not a value sitting inside a box, it is the trail you leave walking from the root to wherever the word ends.

That single idea explains almost everything a trie is good at: fast lookups, cheap prefix matching, and a natural home for autocomplete. It also explains the one thing that trips up almost everyone the first time they use one, which is that a path existing and a word existing are two different facts.

Jump to the interactive trie. It walks insertion, search, prefix search, deletion, and update as one continuous story, but the row of tabs above the canvas jumps straight to whichever operation you want to see on its own.

Nodes are letters, not words

In a plain list of strings, each word is its own self-contained value. A trie throws that away on purpose. Instead, every node holds a single character and a map from 'next letter' to 'next node,' with at most 26 entries if you are working in English. Nothing in the node says what word you are building. That information only exists as the sequence of edges you followed to get there.

The payoff shows up the moment two words share a prefix. Insert CAT, then CAR, then CARD, then CARE, and the demo above only creates new nodes for the letters that do not already exist. C, A, and R get built once, for CAT, and every word after that reuses them. A plain array of strings cannot do this. Each string sits in its own block of memory, so 'CAR' and 'CARD' repeat their first three letters twice, three times, four times, once per word that shares them.

The end-of-word flag is the whole trick

Reaching a node by walking a word's letters only proves that the path exists. It does not prove the word was ever inserted. That is why every node also carries a boolean end-of-word flag, set only when a word actually stops there.

Step through search for CA in the demo and watch this play out directly. C exists. A exists. The path is completely valid. But CA was never inserted as its own word, only as a prefix of CAT, CAR, CARD, and CARE, so its flag was never set. The search correctly reports that CA is not a word, even though every node it needed was sitting right there. That gap between 'the path exists' and 'the word exists' is the single most common bug in a hand-rolled trie, and it is worth internalizing before you write one.

The flag also explains why CAR is not a leaf. CAR ends a word, and CARD and CARE both continue past it. A node can mark the end of one word while still branching into others, because the flag and the children are two independent pieces of state on the same node.

Search fails in exactly two ways

Watch the search steps for CAP and you will see the other failure mode. C exists, A exists, but A has no P child, so the path itself breaks. The search stops immediately and never even gets to check a flag, because there is no node left to check. This is the case that makes tries fast: a lookup for a word that is not there is rejected the moment the mismatched letter shows up, not after scanning anything.

So a trie lookup can fail for two different reasons: the path breaks partway through (CAP), or the path completes but the end-of-word flag is off (CA). Both report 'not found' to the caller, but they are different events inside the structure, and the demo's letter tape colors them differently so you can tell them apart while stepping through.

Prefix search is why tries exist

Everything up to this point, a hash set of strings can also do, and often faster in practice for plain membership checks. The move a hash set cannot make is prefix search, and it is the whole reason tries show up in autocomplete boxes, IDE symbol search, and spell checkers.

Walk the demo's prefix search for CAR. The first three steps just walk C, A, R, exactly like a normal search. The difference is what happens once you arrive: instead of checking one flag, the algorithm runs a small depth-first search over everything below that node and collects every word whose flag is set. For this trie that is CAR, CARD, and CARE, found in a single subtree walk rooted at the node you already reached in three steps.

That is the structural promise of a trie: every word sharing a prefix lives in the same subtree, already grouped, with no scanning of unrelated words required. A hash set has no subtree to walk. It would have to check every single word it holds against the prefix, one at a time.

Deletion only removes what a word owns alone

Deleting a word is not one operation, it is two, and the demo separates them on purpose. First, clear the end-of-word flag on the word's final node. That alone is enough to make the word disappear from search and prefix results, because both of those only ever look at the flag.

Second, walk back up toward the root, deleting nodes, but only while a node has zero children and does not mark some other word. The moment you hit a node that either branches elsewhere or ends a different word, you stop, because deleting it would break something that is still needed.

Delete CAT in the demo and watch this stop early. T gets removed, since nothing else needs it. But A is not removed next, even though CAT is gone, because A still leads to R, which CAR, CARD, and CARE all depend on. Pruning removes exactly the nodes that belonged to CAT and nothing that any other word still relies on.

Updating a word is just delete, then insert

A plain trie has no update primitive of its own, and it does not need one. Renaming a word is exactly deletion followed by insertion, run back to back on the same trie. The demo's update step makes this literal: switch to the Update tab and you will see the delete walk, the unmark, the prune (or the early stop), and then a completely ordinary insertion for the new spelling.

The demo renames CARE to CARS. Both words share the C-A-R prefix, so that half of the path is never touched by either the delete or the insert. Only the last letter changes: E is unmarked and pruned away since nothing else needed it, and S is created fresh under the same CAR node. If the new spelling diverged from the old one earlier, say updating CARE to DOGE, more of the path would be rebuilt, but the mechanism is identical either way: nothing new to learn, just insert and delete composed.

This is also why 'update the value stored at a word' and 'rename a word' are different problems in practice. A trie that maps each word to a value (a dictionary keyed by string, essentially) can update that value in place at the end node without touching the tree at all, since the shape of the trie only encodes which strings exist, not what they are worth. Renaming the string itself, the case this demo covers, is the one that has to move through delete and insert.

What it costs, and when to reach for it

Every operation in this tutorial (insert, search, prefix search, delete, and the delete-plus-insert that makes up update) costs time proportional to the length of the word, not to how many words the trie holds. That is a genuinely different shape of guarantee than a hash set, whose lookup is fast but whose prefix search is not a supported operation at all without scanning everything.

The cost is memory. Every node reserves space for up to 26 children even when it only uses one or two, and short words with little shared structure end up paying for a lot of mostly-empty maps. Production tries usually compress this: a radix trie merges runs of single-child nodes into one edge labeled with a whole substring, and a DAWG (directed acyclic word graph) goes further and merges nodes that lead to identical suffixes. Both are worth knowing exist, but the plain trie in this tutorial is the shape you should understand first, because every compressed variant is just this same idea with extra bookkeeping layered on top.

What to watch for

Step through insertion first and watch which letters create a new node versus reuse one that is already there. That single distinction is what makes a trie memory-efficient for a set of related words. Then step through the three searches back to back: CARD succeeding, CAP breaking mid-path, and CA completing the path but failing the flag check. Once those two failure shapes are visually distinct to you, prefix search, deletion, and update will all make sense as reuses of the same walk, just with a different last step, or in update's case, two of them in a row.

If you only have a minute, use the tabs above the canvas to jump straight to Update and watch CARE become CARS. It is the fastest way to see delete and insert as the same two primitives you already understand, just chained.