Trie (prefix tree)

What it is

A trie is a tree where each edge represents one character and each root-to-node path spells out a prefix. Words that share a prefix share the nodes for that prefix, so the structure encodes an entire dictionary's common structure once instead of once per word. Every operation — insert, exact lookup, "does any word start with this" — is a walk from the root, one character at a time, so its cost depends only on the length of the string being processed, never on how many words are stored. The one detail every implementation needs is a per-node flag (or stored value) marking "a complete word ends here," because a node being reachable is not the same as a word ending there.

When it applies

• You need both exact-match and prefix-match queries against the same growing set of strings — a hash set alone gives you the former for free but forces an O(n) scan for the latter.
• You're searching a grid, board, or text for any of many target strings at once — walking the trie in lockstep with the search keeps all candidates alive simultaneously instead of re-running a single-string search once per target.
• A query pattern includes a wildcard that could match several different next characters — the trie turns that into a branching DFS over children, rather than needing to enumerate every literal string the wildcard could expand to.
• It does not apply when you only ever need exact-match lookups with no prefix or multi-pattern structure — a plain hash set is simpler and just as fast for that case; reach for a trie specifically when prefixes or shared structure matter.

Tells in the problem

• "Support insert, and search-for-exact-word, and starts-with-a-prefix" — the textbook three-operation trie, where the terminal flag is what separates the second operation from the third.
• "Find all dictionary words present in a grid/board" — one trie shared across every DFS start point, with pruning (deleting exhausted branches) as the difference between a correct and a fast solution.
• "Support a wildcard character that matches any single letter" — a DFS over trie children at the wildcard position, trying every branch instead of following one.
• "Autocomplete" or "suggest completions for what's typed so far" — walk to the prefix's node, then explore (or read a precomputed list from) the subtree below it.
• Large numbers of strings sharing significant prefix overlap (words, URLs, file paths) where memory or lookup speed for prefix-shaped queries is explicitly a concern — a strong signal to reach for prefix-sharing structure over a flat collection.

The classic mistake

The most common bug is forgetting the terminal flag entirely, or checking only "did the walk reach a node" instead of "did the walk reach a node marked as a complete word" — this makes search("app") incorrectly return true after only "apple" has been inserted, because the path exists even though no word ends exactly there. A second common mistake shows up in multi-word search over a grid or board: running a fresh single-word search once per target word, which throws away the fact that many target words share prefixes and forces the same cells to be explored repeatedly. The fix in both cases is the same instinct — treat "the path exists" and "a word ends here" as two separate questions the trie must answer, and let one shared trie serve every query instead of rebuilding structure per query.

Questions to start with

• Implement Trie (Prefix Tree) — the three core operations and the terminal-flag distinction that the whole pattern rests on.
• Design Add and Search Words Data Structure — the same trie with a wildcard added, turning single-child traversal into a branching DFS.
• Word Search II — one trie shared across every grid start cell, plus the pruning (dead-branch deletion, found-word clearing) that keeps a many-words search fast.
• Design Search Autocomplete — the trie reframed as a system component: precomputed top-k lists per node, sharded and served from memory at scale.