Top 14 LeetCode Trie Problems for Coding Interviews

You spent weeks grinding patterns. Sliding window, two pointers, dynamic programming. You feel ready. Then someone asks you to "implement autocomplete" and your brain does a full factory reset.

Tries. They show up in maybe 5% of interviews and get roughly 0% of practice time. This guide fixes that. Fourteen LeetCode trie problems in order from foundational to genuinely painful, with the specific insight each one teaches and the trap that swallows candidates whole.

Work through these in order. The patterns build on each other in ways that matter.

The Whole Data Structure Is Two Fields

A trie node holds exactly two things: a dict (or array of 26) mapping characters to children, and a boolean is_end. Every insert traces a path from root to the last character and flips is_end = True. Search walks the same path and checks is_end. StartsWith checks only that the path exists.

What changes across all 14 problems is what you augment the node with, and which direction you walk.

Trie structure storing "app", "apple", "apply", and "ape". The is_end flag marks where words terminate.

For a deeper refresher, the trie data structure guide covers the full mechanics. For help spotting trie problems from the constraints alone, see recognizing trie problem signals.

The Foundation: Get This Right Before Anything Else

1. Implement Trie (LC 208, Medium)

Before you do anything else, build it cold. No looking at solutions. Implement insert, search, and startsWith from scratch.

The critical distinction: search checks is_end, but startsWith only checks the path exists. It sounds obvious. Under interview pressure, with someone watching, it evaporates instantly. Do not move to problem 2 until you can write this in under 10 minutes without hesitation.

2. Replace Words (LC 648, Medium)

You have a list of root words. For each word in a sentence, replace it with the shortest matching root. "Cat" in the dictionary turns "cattle" into "cat".

The only thing this problem tests: stop walking as soon as you hit an is_end = True node. Walk to the end of the word first and you get wrong answers silently. That is it. That is the entire problem. And it is the one bug candidates consistently ship to production.

Five Problems That Cover Every Core Pattern

3. Longest Word in Dictionary (LC 720, Medium)

Find the longest word where every prefix also exists in the dictionary. "Apple" qualifies only if "a", "ap", "app", "appl", and "apple" all exist as separate entries.

is_end acts as a traversal gate here, not just a terminal marker. During BFS or DFS, only follow edges that lead to is_end = True nodes. This flips the mental model from "check is_end at the destination" to "filter on is_end during traversal." That flip comes up again on the harder problems.

4. Search Suggestions System (LC 1268, Medium)

After each character typed, return the top 3 lexicographically smallest matching product names. This is autocomplete.

Sort the products before inserting them, then store at most 3 product indices at each node. Because you sort first, the first three you encounter at any node are automatically the lexicographically smallest. Query time per prefix drops to O(L). This is the autocomplete template. Memorize it.

5. Map Sum Pairs (LC 677, Medium)

Insert key-value pairs. Query for the sum of all values whose keys share a given prefix.

First augmented trie in the list. Each node stores a cumulative sum that updates on insert: for every node on the path, add new_val - old_val for that key. The delta handles re-insertion correctly. Queries become a single walk to the prefix node and a value read. The trie is computing something beyond character matching now.

6. Add and Search Words (LC 211, Medium)

Like a basic trie, except search supports . as a wildcard that matches any single character.

When you hit ., branch into every non-null child and recurse down each one. The trap: returning true on the first match instead of exploring all children. Get the wildcard DFS right here. If your branching logic is wrong on LC 211, it fails in harder and stranger ways on LC 212.

7. Word Break (LC 139, Medium)

Given a string and a word dictionary, can the string be segmented into dictionary words?

Solvable with DP and a hash set. Combining a trie with DP is cleaner at scale. Build a trie from the dictionary, then run DP where dp[i] is true if s[:i] can be segmented. For each valid start i, walk the trie from s[i] forward and mark dp[j] true whenever you land on an is_end node. The trie walk replaces the inner substring loop. One traversal, all prefix matches found.

For more on pairing DP with data structures, see when to use dynamic programming.

The One That Looks Nothing Like a String Problem

8. Maximum XOR of Two Numbers in an Array (LC 421, Medium)

Given an integer array, find the maximum XOR of any two elements.

You stare at this problem. You think about sorting. You think about hash sets. Nothing obvious appears. Then someone tells you "binary trie" and everything clicks. Build a trie where each number is stored bit by bit, MSB first, 32 levels deep. For each number, greedily pick the opposite bit at each level when it exists in the trie. Opposite bit means XOR bit set to 1, maximizing the contribution at each position. O(n²) brute force becomes O(32n).

If you have not seen binary tries before, this problem looks genuinely impossible. Once you see it, you will never forget it. It is the single best example of "tries are not just for strings."

When the Trie Goes Into a Grid

9. Word Search II (LC 212, Hard)

Given a 2D board and a list of words, find all words that can be formed by adjacent characters.

Build a trie from the word list. Run DFS from every cell, advancing the trie pointer with each step. When you land on is_end = True, immediately set is_end = False to prevent duplicates and prune future DFS branches for that word. Without this, completed words get re-explored on every path that passes through the same characters. The solution runs forever. The pruning is what takes this from TLE to AC.

This is the most common FAANG trie problem. It is also the one that catches everyone who got LC 211 right but skipped the is_end pruning. The wildcard DFS from problem 6 gets you to the grid DFS here. The patterns compound.

For the DFS mechanics this problem depends on, see the DFS pattern recognition guide.

Hard Tier: Two Ideas at Once

The next five problems require a trie plus one more technique. You have to hold both ideas simultaneously. This is where the interview gets interesting.

10. Prefix and Suffix Search (LC 745, Hard)

Support queries with both a prefix and a suffix. Return the largest index of any word matching both.

For each word, insert every suffix + '#' + word combination into a single trie. For "apple" you insert "#apple", "e#apple", "le#apple", "ple#apple", "pple#apple", and "apple#apple". A query for prefix "app" and suffix "le" becomes the lookup "le#app". Each node stores the largest word index it has seen. Build cost: O(n × L²). Query cost: O(P + S). This is a construction trick, not a traversal trick. Most candidates see the problem and freeze. The encoding is the whole thing.

11. Stream of Characters (LC 1032, Hard)

Characters arrive one at a time. After each character, return true if any dictionary word ends at the current position in the stream.

Scanning all words against a growing buffer is too slow. Reverse all dictionary words and build a reversed trie. On each new character, maintain a set of active trie nodes. Add the root on every character (a new potential match starts here), advance every active node by the new character, discard nodes with no matching child. If any active node hits is_end, return true. The reversed trie converts suffix matching into prefix matching. Each query runs in time proportional to active nodes, bounded by dictionary size.

12. Word Break II (LC 140, Hard)

Like Word Break, but return all possible segmentations instead of just a boolean.

DP tells you segmentation is possible but cannot reconstruct all paths. Build a trie, then backtrack: at each position, walk the trie and recurse whenever you hit is_end = True, carrying the partial sentence forward. Memoization helps when many positions share overlapping completions, but the branching factor is still exponential on adversarial inputs. This is LC 139 turned inside out. If your trie walk was clean on problem 7, the same walk drives this backtracking.

13. Palindrome Pairs (LC 336, Hard)

Find all index pairs (i, j) such that words[i] + words[j] is a palindrome.

Build a trie of reversed words. For each word, walk the trie and handle three cases: the trie word is shorter and the remaining suffix of the query is a palindrome; the trie word is longer and the unmatched trie portion is a palindrome; and the exact reverse match. The reversed trie converts the O(n × L²) hash-set approach into one trie walk per word. Most candidates handle the exact reverse case and miss the other two. If you miss either of the partial-match cases, your solution passes 60% of test cases and then silently fails.

14. Concatenated Words (LC 472, Hard)

Find every word in the list that can be formed by concatenating two or more other words from the same list.

Build a trie from all words, then run Word Break DFS on each candidate with one constraint added: the final segment cannot be the word itself. Track the segment count and require at least two components. The dictionary is the input list itself. LC 139 is a hard prerequisite here. If you do not have Word Break clean, do not attempt this one first.

All 14 at a Glance

Problem	Difficulty	Core Pattern
208 Implement Trie	Medium	Foundation: insert, search, startsWith
648 Replace Words	Medium	Stop at first `is_end`
720 Longest Word in Dictionary	Medium	Traverse only `is_end` nodes
1268 Search Suggestions System	Medium	Sorted insert, store top 3 per node
677 Map Sum Pairs	Medium	Augmented node with cumulative value
211 Add and Search Words	Medium	Wildcard `.` branches to all children
139 Word Break	Medium	Trie walk drives DP transitions
421 Maximum XOR	Medium	Binary trie, greedy opposite-bit selection
212 Word Search II	Hard	Grid DFS + trie, prune `is_end` on match
745 Prefix and Suffix Search	Hard	`suffix#word` encoding into single trie
1032 Stream of Characters	Hard	Reversed trie + active node set
140 Word Break II	Hard	Trie walk drives backtracking
336 Palindrome Pairs	Hard	Reversed trie + three-case analysis
472 Concatenated Words	Hard	Trie + word-break DFS, segment count

The Five Traps That Keep Coming Back

You will hit these. Everyone does.

Checking is_end at the end instead of during traversal. Kills Replace Words and Longest Word in Dictionary.
Not branching over all children for .. Kills Add and Search Words and every wildcard DFS built on top of it.
Not setting is_end = False after finding a word. Word Search II either times out or returns duplicates.
Missing the suffix#word encoding. Prefix and Suffix Search looks completely unsolvable without it. That is not a skill issue. It is a pattern recognition issue.
Returning true on the first segment in Concatenated Words. The problem requires at least two components. Easy mistake, zero partial credit.

Practice the Explanation, Not Just the Code

These 14 problems cover every trie variant that shows up in real interviews: augmented nodes, wildcard branching, key encoding, binary tries, multi-technique hard problems. Work through them in order. The mental toolkit stacks.

A few non-obvious things before you move on. LC 421 (binary trie) and LC 745 (encoding trick) require the most lateral thinking and appear where candidates least expect them. The hard problems almost always pair a trie with a second technique. And pruning is_end = False in LC 212 is the single most impactful line in this entire list.

Knowing the approach and explaining it under pressure are genuinely different skills. SpaceComplexity runs voice-based DSA mock interviews with rubric feedback so you practice narrating the pruning logic and the binary trie greedy walk out loud, not just in a text editor.