Tries

A trie answers one specific question efficiently that a hash set can't: not just "have I seen this exact string," but "have I seen anything that starts this way." Every problem in this topic is some variation of exploiting that — prefix lookup, prefix-based aggregation, or walking multiple candidate strings at once because they share structure.

What a trie actually is

A trie is a tree where each edge represents one character, and each root-to-node path represents the prefix spelled out by the characters along the way. A node marks "a complete word ends here" with a flag — critically, a node being reachable (someone walked through it) is not the same as a node being an endpoint (some inserted word actually ends there). Confusing "this prefix exists" with "this exact word was inserted" is the single most common trie bug, and Implement Trie's search vs. starts_with distinction exists specifically to force you to keep them separate.

A trie node can hold more than just a flag

Most first examples only ever store a boolean "is this a complete word." Map Sum Pairs breaks that assumption immediately: every node instead accumulates a running sum of every value inserted through it, so a prefix query is a single O(L) walk instead of enumerating and summing every matching key. Word Search II's trie nodes store the actual word string at completion points, so a match reports itself directly without needing to reconstruct the path. The lesson: a trie node is just a bucket you can attach whatever aggregate the problem needs to — it doesn't have to be limited to a flag.

The alphabet doesn't have to be letters

Maximum XOR of Two Numbers in an Array is the clearest proof that "trie" doesn't mean "strings." Insert each number's binary representation, one bit at a time, into a trie with exactly 2 children per node instead of 26 — the exact same structure, just a 2-symbol alphabet instead of a 26-symbol one. Once you see this, you can build a trie over anything with a fixed, ordered set of "next symbol" choices — it's a general prefix-matching structure, strings are just the most common alphabet.

// A string trie: 26 possible next characters.
struct StringTrieNode { StringTrieNode* children[26] = {}; bool is_end = false; };

// A bit trie: exactly the same idea, only 2 possible next bits.
struct BitTrieNode { BitTrieNode* children[2] = {}; };
// Walking bit-by-bit (most significant first) and greedily choosing the
// OPPOSITE bit at each level is what maximizes XOR -- the trie just needs
// to answer "does a number with this bit prefix exist," same as any
// string trie answers "does a word with this letter prefix exist."

Multiple candidate strings, walked together

Word Search II is the clearest case for "why build one shared trie instead of searching separately." A naive per-word DFS repeats the exact same board exploration once per word, even for words sharing a prefix. Building one trie from every word and walking the board and trie together means shared prefixes are only ever explored once — the trie itself is what lets many separate searches collapse into a single pass.

Common mistakes

• Treating "reachable" as "a complete word" — a node existing because some longer word passes through it doesn't mean that exact prefix was itself inserted as a word (Implement Trie's whole point).
• Extracting and hashing substrings instead of walking the trie incrementally — Index Pairs of a String and Concatenated Words both specifically avoid building a fresh substring at every candidate split point, walking trie nodes directly instead — the difference between O(n · maxWordLength) and O(n² · avgWordLength).
• Forgetting a node can hold more than a boolean — Map Sum Pairs needs a running sum at every node, not just at the end; missing this turns an O(L) prefix query back into an O(matching keys) enumeration.
• Not handling the overwrite case in aggregating structures — Map Sum Pairs must propagate a *delta* (new minus old value) up the whole path on a re-insert, not just add the new value, or every ancestor's sum silently drifts wrong.