Trie Interview Problems: 12 That Cover Every Pattern

You open LeetCode. You see "Word Search II." You think: grid DFS, I've done this before. You submit. Time Limit Exceeded. You add some pruning. TLE again. You read the editorial. It uses a trie. Of course it uses a trie.

That moment is why these 12 problems exist in order. Almost every trie interview problem reduces to the same three moves: insert, traverse to a prefix, collect. The variation is in what you collect, how you modify the structure, and what you combine it with.

Work through them in order. The early ones lock in the mental model, grounded in the trie data structure itself. The hard ones combine trie with DFS, backtracking, and bit manipulation, and none of them make sense without the groundwork.

The 12 at a Glance

#	Problem	Difficulty	Core Pattern
1	Implement Trie (208)	Medium	Core structure
2	Replace Words (648)	Medium	Prefix replacement
3	Search Suggestions System (1268)	Medium	Sorted prefix walk
4	Short Encoding of Words (820)	Medium	Suffix trie
5	Sum of Prefix Scores (2416)	Medium	Count pass-throughs
6	Maximum XOR of Two Numbers (421)	Medium	Binary trie
7	Add and Search Words (211)	Medium	Wildcard DFS
8	Concatenated Words (472)	Hard	Decomposition + memo
9	Word Search II (212)	Hard	Trie + grid DFS
10	Palindrome Pairs (336)	Hard	Reversed trie
11	Design Autocomplete System (642)	Hard	Frequency-ranked retrieval
12	Word Squares (425)	Hard	Constraint propagation

1. Implement Trie (208)

Every other problem on this list assumes you have internalized this one. Not vaguely recognized it. Not watched a video about it while half-paying attention. Internalized it, to the point where you can write the node structure from memory at 9am on a Zoom call.

A TrieNode holds a dictionary of children and an is_end flag. Insert walks character by character, creating nodes as needed. Search is the same walk, returning is_end at the terminal node. startsWith is just search without the is_end check.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

The interview trap: forgetting that search("app") should return False when only "apple" was inserted. is_end is what distinguishes a prefix from a complete word. Get this wrong and every problem after it breaks in a subtly different way each time.

2. Replace Words (648)

Return on the first complete match, not the deepest one.

Build a trie from all roots. For each word in the sentence, walk the trie character by character. The moment you land on a node with is_end = True, stop and return what you have so far. That is the shortest root. If you reach the end of the word without a match, keep the original.

The trie is a filter you exit early. This pattern reappears whenever you want the shortest prefix that satisfies a condition.

3. Search Suggestions System (1268)

Sort before inserting and you never need a heap.

Sort the word list once upfront. Then, for each character of the search prefix, walk one node deeper and DFS to collect the first three words you encounter. DFS on a sorted trie yields lexicographic order automatically.

You do not need any sorting after insertion. Sorting upfront lets you collect results in order during traversal. Remember this whenever a problem asks for lexicographically smallest results from a trie.

4. Short Encoding of Words (820)

When the constraint is about suffixes, reverse the input.

A word needs its own encoding slot only if it is not a suffix of another word. Reverse every word and insert into a trie. A word is standalone if and only if its reversed version ends at a leaf. Walk all leaves, sum path_length + 1 (for the # separator). Done.

The reversal trick: whenever a problem is framed around suffixes rather than prefixes, reversing the input and using a standard trie is usually the cleanest path.

5. Sum of Prefix Scores of Strings (2416)

Embed the aggregate at write time so queries are just a path sum.

Each TrieNode carries a count field. Every time you pass through a node during an insert, increment it. To query a word's prefix score, walk its characters and sum the counts.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0   # words that passed through this node

This is the "count on insert" pattern. It generalizes anywhere you need to aggregate a property across all strings sharing a prefix.

6. Maximum XOR of Two Numbers in an Array (421)

Children are 0 and 1. You go the opposite direction.

Insert every number bit by bit, most significant bit first. To maximize XOR with a query, greedily follow the opposite child at every level. If you want a 1 in position k, look for a child with value 0. Fall back to the same child if necessary.

This is the canonical binary trie pattern. It generalizes to any problem asking you to maximize or minimize a bitwise operation over a set of numbers.

7. Add and Search Words (211)

A . character breaks the linear path. Now you need DFS.

Normal search follows one path. A . can match any child, so you must try every child and continue recursively. This turns search into a DFS on the trie itself. It's only about 15 lines of code, but the mental shift matters: a trie traversal is not always a single path.

def _search(self, word, idx, node):
    if idx == len(word):
        return node.is_end
    ch = word[idx]
    if ch == '.':
        return any(self._search(word, idx + 1, child)
                   for child in node.children.values())
    if ch not in node.children:
        return False
    return self._search(word, idx + 1, node.children[ch])

A trie search is not always a single path. Wildcards split it into multiple branches. This mental model is essential for Word Search II, so make sure it clicks here before moving on.

8. Concatenated Words (472)

Use the trie as a vocabulary for word decomposition, combined with memoization.

Build a trie from all words. For each word, check if it can be split into two or more words that also exist in the trie, using DFS with memoization. At every position, walk the trie until you hit an is_end node, then recursively check the remainder.

The gotcha: a word cannot be composed entirely of itself. Track whether you have made at least one cut before accepting a full match.

9. Word Search II (212)

This is the problem from the opener. The one people try to brute-force, get TLE on, and then discover needs a trie. With a trie but without the pruning step, it still times out. There is exactly one way to pass this.

Build a trie from the word list. Run depth-first search on every grid cell, maintaining a pointer into the trie. If the current cell's character is not a child of the current node, stop immediately. Record a word when you reach an is_end node.

The critical pruning step: once a word is found, delete it from the trie (set is_end = False and clean up empty nodes). This prevents re-finding the same word and removes dead branches. Without it, the solution times out on large inputs.

This is the hardest problem here to implement correctly under time pressure. Practice the pruning step on its own before putting it in a full solution.

10. Palindrome Pairs (336)

Two cases. Most solutions miss one.

Insert all words reversed. For each word w, you want words v such that w + v or v + w is a palindrome. Case 1 (w is longer): walk the trie with w's characters, and at every is_end node check if the remaining suffix of w is a palindrome. Case 2 (v is longer): walk the trie with w, reach a match, then check if the remaining trie path is a palindrome prefix.

This is the hardest problem on the list. Work through both cases on paper before writing a line of code, test the empty-string edge case explicitly, and accept that your first attempt will probably be wrong. That is normal. The structure is genuinely subtle.

11. Design Search Autocomplete System (642)

Frequency tracking at every node, with a real space-vs-query trade-off to discuss.

Each TrieNode stores a {sentence: count} map for all sentences that pass through it. On input(c), extend the current prefix and return the top 3 by count (ties broken alphabetically). On '#', insert the completed sentence and increment counts up the path.

Know both approaches: storing the full frequency map at each node makes prefix queries O(1) but is space-heavy. DFS on each query is cheaper in space but O(n) per query. Interviewers at companies with autocomplete products ask about this explicitly.

12. Word Squares (425)

The trie is not the solver. It is the oracle that makes backtracking fast enough to work.

A word square: the k-th row and k-th column match. Use backtracking to fill each row. Before placing row i, determine the required prefix: it is the i-th character of each word already placed. Look up all words with that prefix in the trie, try each one, recurse.

Row 0: "ball"   -> col prefixes become "b", "a", "l", "l"
Row 1: starts with "a" -> try "area"
Row 2: starts with "ll" -> ...

This is constraint propagation. The trie only offers valid candidates at each step, pruning the search space before you recurse. The pattern appears broadly in backtracking problems.

How to Study Trie Interview Problems

Work them in order. Problems 1 through 7 each add exactly one new mechanic. Do not jump to Word Search II before you can write Add and Search Words cleanly from memory. If you are new to tries, Trie Problems Leave Clues is worth reading first.

For problems 8 through 12, draw the trie before touching a code editor. Label the nodes. Trace a small example by hand. Implementation failures on these almost always trace back to a misunderstood case, not a typo. The people who open VS Code first and draw later are the ones who spend an hour debugging a palindrome case they never thought through.

Where candidates actually stumble:

208: Write this from scratch three times until the node structure is automatic. Not two. Three.
212: Time yourself specifically on the pruning step. Most implementations skip it, get TLE, and add it as an afterthought.
336: Map out both palindrome cases on paper before writing anything. Seriously, on paper.
421: Practice bit manipulation separately if binary tries feel unfamiliar.

If you want to work through these under realistic interview pressure, SpaceComplexity runs voice-based mock interviews that force you to explain your trie traversal out loud. Silent practice on these problems misses a lot.

What to Take From This

Insert + traverse + collect is the core loop. Everything else is variation.
Reverse the input when the constraint is about suffixes, not prefixes.
Augment nodes at insertion time so queries stay cheap.
Binary trie: children are 0 and 1, greedy traversal maximizes XOR.
Wildcards turn a linear search into a trie DFS.
Word Search II and Word Squares use trie as a pruning layer, not the primary search.
Palindrome Pairs requires explicit case enumeration. Draw both cases first.