Type "ca" into your phone's contacts search and it instantly shows "Carl," "Carol," and "Cathy." That's a trie at work: a tree built for exactly one job, answering "what starts with this prefix?" Autocomplete, spell-check, IP routing tables, and word-search puzzles all reduce to that same question, one a hash table answers poorly since it can only match whole keys, not prefixes. This lesson builds a trie from scratch, then uses it on two escalating problems, one of them a hard.

What a trie node holds

Each node represents one character position. It holds links to its children, one per possible next character, plus a flag marking "a word ends here."

A path from the root spelling c-a-t represents the word "cat". Words that share a prefix share nodes: "cat" and "car" both walk c -> a, then split at the third letter. That sharing is exactly what makes prefix queries cheap; you're not comparing "cat" against "car" character by character, you're walking one shared path and branching only where the words actually differ.

Remember: a trie node is a character position, not a whole word. Shared prefixes share the same nodes.

Insert, search, and prefix search

All three operations walk the tree one character at a time: O(m), where m is the length of the word or prefix. That cost never depends on how many other words are already stored, only on the length of what you're looking up.

The detail that trips people up: search needs is_end_of_word == True at the final node, meaning the exact word was inserted. startsWith only needs the path to exist; some word starting with this prefix was inserted, but the prefix itself might not be a whole word on its own. Mixing these two up is the most common trie bug.

Remember: search needs the path AND the end-of-word flag. startsWith needs only the path.

Trading memory for speed

A naive trie node using a fixed 26-slot array (children = [None] * 26) wastes memory whenever the alphabet in a given subtree is small or sparse. A dict-based node (children = {}) only allocates entries for characters actually present, at the cost of slightly slower lookups: hashing instead of a direct array index.

A further optimization for memory-constrained cases is the compressed trie (radix tree): it merges chains of single-child nodes into one edge labeled with a substring instead of one character, cutting node count sharply for tries with many long, unique suffixes. You're rarely asked to implement this in an interview, but naming it is worth doing if asked how you'd scale a trie to millions of entries.

Remember: array children are faster but always cost 26 slots; dict children only pay for characters actually used.

Implement Trie

LeetCode 208 — Trie — Basic implementation

This problem is the concept section above, asked as a standalone exercise: build insert, search, and startsWith directly.

Approach: TrieNode holds a children dict and an end-of-word flag. insert walks or creates nodes as needed. search and startsWith walk and check existence; search additionally checks the end-of-word flag.

Complexity: insert/search/startsWith are all O(m) time, where m is the word or prefix length. Space O(total characters across all inserted words) in the worst case, when no prefixes are shared.

Common mistakes: Returning True from search just because the path exists, forgetting the end-of-word check. Also, unconditionally writing node.children[ch] = TrieNode() on insert instead of checking first, which wipes out existing subtrees and loses previously inserted words.

Remember: this problem IS the concept section. If you can write insert/search/startsWith from memory, you know tries.

Word Search II

LeetCode 212 — Trie + Backtracking — Hard

Searching the board separately for each word in a word list, one full DFS per word, is far too slow when both the board and the word list are large. Instead, build one trie from every word, then run a single DFS pass over the board, walking the trie and the board together, step for step. This shares work across words with common prefixes and lets you prune a board path the instant it stops matching any word's prefix.

Approach: Build a trie from words (mark word ends). DFS from every board cell; at each step, only continue if the current character exists as a trie child of the current trie node. When a trie node marks a complete word, record it (and mark that trie node as spent, to avoid duplicate results). Backtrack the board cell after exploring.

Complexity: Time O(rows × cols × 4^L) in the worst case (L = longest word length), but trie pruning, stopping as soon as no word's prefix matches and removing exhausted branches, makes it far faster in practice than a per-word DFS. Space O(total trie nodes + recursion depth).

Common mistakes: Running a separate DFS search per word instead of one shared trie-guided DFS. Correct, but too slow for the hard-tier constraints. Forgetting to backtrack the board mutation after recursion, which corrupts later searches. Skipping the guard against duplicate results when the same word can be found via multiple paths; resetting the end-of-word flag after the first match handles this.

Remember: one trie built from all words, one shared DFS over the board, pruning dead branches as you go.

Replace Words

LeetCode 648 — Trie

For each word in a sentence, find its shortest dictionary root, if one exists, and swap the word for that root. A trie built from the roots lets you walk each word one character at a time and stop at the very first end-of-word flag you hit, which is automatically the shortest matching root.

Approach: Insert all roots into a trie. For each word in the sentence, walk the trie; the moment you hit an end-of-word flag (or run out of characters or trie path), replace the word with the prefix walked so far, or keep the original word if no root matched.

Complexity: Time O(total characters in the dictionary + total characters in the sentence), space O(total characters in the dictionary) for the trie.

Common mistakes: Not stopping at the first end-of-word flag reached. The problem wants the shortest matching root, so continuing past it would wrongly look for a longer one. Also, using a naive "try every root as a prefix" approach with string methods, which is O(words × roots × root length) instead of the trie's near-linear scan.

Remember: stop at the first end-of-word flag you hit while walking down; that's always the shortest matching root.

Maximum XOR of Two Numbers in an Array

LeetCode 421 — Trie — Hard

To maximize the XOR of two numbers, you want their bits to differ at the highest positions possible, since a higher bit position contributes more to the result. A binary trie, where each node has at most 2 children (bit 0 or bit 1), lets you, for each number, greedily walk toward the opposite bit at every position. That greedy walk finds the best XOR partner for that number in O(32) steps instead of comparing it against every other number. It's the same prefix-tree idea from earlier in this lesson, applied to bits instead of letters.

Approach: Insert every number into a binary trie, most-significant-bit first (fixed 32-bit width). For each number, walk the trie trying to go the opposite direction of each of its bits; when the opposite branch doesn't exist, take the only branch available. Track the best XOR found.

Complexity: Time O(n × 32) = O(n), space O(n × 32) for the trie nodes. Far better than the naive O(n²) pairwise XOR comparison.

Common mistakes: Iterating bits least-significant-first instead of most-significant-first. The greedy "prefer the opposite bit" strategy only produces the true maximum when higher bit positions are locked in before lower ones. Also, forgetting a fixed bit width, which lets negative numbers or inconsistent trie depths break the comparisons.

Remember: a binary trie over bits, most significant first, walking toward the opposite bit at every step, turns "best XOR partner" into an O(32) walk.