Trie

The problem it solves

Store a dictionary so that prefix questions are cheap. A hash set answers “is card a word?” in one hash — and is completely mute on “what starts with car?”, “is anything here a prefix of this string?”, or “list the words in order”. Those questions power autocomplete, spell-check suggestions, IP routing (longest-prefix match is how routers choose next hops), T9 keypads, and word-game solvers — and they all fall to the same structure: a tree where each edge is one character, so each node is the prefix spelled by the path from the root.

The trie’s headline guarantee is easy to under-appreciate: lookup, insert, and prefix queries cost O(L) where L is the word’s length — the size of the dictionary never appears. A trie holding fifty million words answers “is card stored?” in exactly four edge-hops, the same four it would take in a trie holding ten. Structures whose query cost depends only on the query are rare, and interviews use the trie to test whether a candidate can see when that trade is the right one — and when a plain hash map embarrasses it.

The intuition — and where it breaks down

A filing system where the first letter picks the cabinet, the second picks the drawer, the third the folder. Words that share a beginning share the walk: cat, car, card, care all travel the same c → a spine before parting ways, and that shared spine is stored once. Inserting care into a trie that already holds car creates exactly one new node — the e — because everything else already exists. The player’s first prediction prompt asks exactly this count, because computing it forces the central realisation: the structure is the sharing.

The intuition’s famous trap: reaching the end of a path is not the same as finding a word. Store cat, then search ca — the walk succeeds, every letter has an edge, and yet ca was never stored; it is a stem, present only as scaffolding for cat. Every node therefore carries a one-bit flag — “a word ends here” — and search checks it where startsWith does not. That single bit is the entire difference between the two operations, it is invisible in the tree’s shape (the drawing inks flagged nodes for exactly this reason), and forgetting it is the most common trie bug in existence.

Where the picture breaks down economically: the filing-system image suggests compactness, but a naive trie is memory-hungry — one node per character, each holding a child table. Disjoint words share nothing and cost a chain apiece (the disjoint preset shows the degenerate case: a trie that is just a list of chains, all overhead and no sharing). The structure pays for itself in proportion to how much prefix-sharing the data actually has.

Loading…

A walkthrough you can check

Insert cat, car, card, care, dog, do, then search.

1. cat: three new nodes — c, ca, cat; flag cat.
2. car: walks c, a (existing), spawns r. One new node for a three-letter word.
3. card, care: each walks car, spawns one node. The ca spine now serves four words.
4. dog: no sharing with the c-branch — three new nodes. do: zero new nodes; it flags an existing stem. A word can arrive without creating anything.
5. Search car: c → a → r, flag set — found. Search ca: path exists, flag absent — not stored (the trap, sprung). Search dot: d → o, then no t edge — the walk dies mid-word, which is the other way a search fails.

Count the tree: 11 nodes (plus the root) store six words totalling 19 characters — the unit suite pins this exact arithmetic: nodes = distinct prefixes. Both failure modes and the sharing count are things you can now verify by looking at the drawing, which is the point of drawing it.

The invariant

Each node is uniquely identified by the string spelled from the root to it; the trie contains exactly one node per distinct prefix of the stored words; and a string is stored iff its path exists and ends flagged. Insertion preserves all three: it walks existing prefix nodes (creating none — uniqueness), spawns nodes only for prefixes that did not exist (exactly-one-per-prefix), and sets the flag at the full word’s node (membership). Search consults precisely the invariant’s third clause: path and flag.

Two consequences fall out. Lexicographic iteration is a depth-first walk taking child edges in alphabetical order — the trie is a sorted structure for free, which hash maps can never be. And deletion is subtler than it looks: unflag the node, then prune upward only while nodes are flagless and childless — stopping the prune at shared structure is exactly the third pitfall below.

Complexity, derived

Insert and search touch one node per character: O(L) each, with the per-node child lookup O(1) for array children or expected O(1) for hashed children. Prefix queries: O(L) to reach the prefix node, then output-sized work to enumerate beneath it. No n anywhere — the dictionary’s size affects memory, never per-query time.

Memory is the honest cost: O(total characters) nodes in the worst case (no sharing), each with a child table. Array-of-26 children make lookups branchless but cost 26 pointers per node — ruinous for sparse alphabets or Unicode; hash-map children are compact but slower. Compressed tries (radix / PATRICIA trees) collapse single-child chains into multi-character edges, cutting node counts drastically — the production form, and the one inside routing tables. Compared head-to-head with a hash set on pure membership tests, the hash set usually wins on constants and memory; the trie’s case is the prefix operations, and saying so unprompted is the mark of understanding the trade rather than the structure.

What people get wrong

• Path-exists ≠ word-stored: returning true without checking the flag — the ca trap. The single most common bug, and the player’s prediction question.
• 26-slot arrays for open alphabets: works on lowercase test data, detonates on Unicode. Child storage must match the alphabet.
• Deleting shared structure: removing car must not remove the ca spine that cat, card and care still need. Prune only flagless, childless nodes, bottom-up.
• Rebuilding string keys per node: concatenating the prefix at every step turns O(L) into O(L²). Carry the position, not the string.
• Reaching for a trie on whole-word-only workloads: if no query is prefix-shaped, a hash set is simpler, smaller and faster — the trie is a specialist, not an upgrade.

Implementation notes

A node needs two members: a child table and a boolean. Children as Map/dict for general alphabets; as a 26-array (ch - 'a') when the problem guarantees lowercase — say the assumption out loud when making it. Insert iteratively: walk, create-on-miss, flag at the end. Search identically minus creation, returning the flag; startsWith returns path-existence. All three are ten lines, and the sources panel keeps them line-matched across languages.

The two upgrades worth knowing by name. Radix compression: collapse single-child runs into string-labelled edges — same asymptotics, far fewer nodes, and the form used by routing tables and PATRICIA indexes. Aho–Corasick: a trie of patterns plus failure links (BFS-computed), turning multi-pattern text search into a single linear scan — the trie as an automaton, and the bridge to the string-matching family.

For word games and autocomplete ranking, augment nodes with counts (words beneath) or best-completion pointers, maintained on insert — the same augmentation discipline as order-statistic BSTs. And for the interview classic “design search autocomplete”: trie to the prefix node, then a bounded DFS (or precomputed top-k per node) beneath it — both halves of this page’s content in one question.

The follow-up questions

Trie versus hash map — when does each win? Hash map: whole-string membership, better constants and memory. Trie: anything prefix-shaped — startsWith, autocomplete, longest-prefix match, sorted iteration — which hashing cannot express at all.

Why the word flag? Every prefix of a stored word traces a complete path, so path-existence proves prefix-hood, not membership. The flag is the difference between search and startsWith.

How does deletion work safely? Unflag the terminal node, then prune upward while nodes have no flag and no children. The stopping condition protects shared spines.

Where do tries run in production? IP routing (longest-prefix match over bit-tries), autocomplete backends, spell-checkers, T9, and — in compressed and automaton forms — PATRICIA indexes and Aho–Corasick multi-pattern scanners inside intrusion-detection systems.