Trie (Prefix Tree): Practice Problems with Solutions
Welcome to the practice problems for the trie. If you need a refresher on the code, the concept guide covers the intuition and the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.
Recommended Study Order
The problems are ordered by difficulty, but the progression matters as much as the individual solutions.
- Implement Trie (Prefix Tree) teaches the core structure: the descent loop and the end marker. Master this before adding anything else.
- Design Add and Search Words Data Structure turns search into recursion. Wildcards force you to branch at the node level instead of walking a straight path.
- Replace Words is the first problem where the trie is a helper inside a bigger task. The pattern stops being the whole answer and becomes a tool.
- Longest Word in Dictionary adds depth-first enumeration, and the end marker starts acting as a gate that controls which branches count.
- Implement Magic Dictionary gives the search a budget of exactly one mismatch. This is the wildcard idea from problem 2 with a constraint attached.
- Word Search II combines the trie with grid backtracking. It is the first problem where two patterns work together.
- Concatenated Words layers dynamic programming with memoization on top of the trie. It is the hardest problem in the set because it uses the trie as a lookup table inside a search over splits.
Easy Problems
1. Implement Trie (Prefix Tree)
LeetCode 208 | Difficulty: Easy
Brief: Implement a trie with insert, search, and startsWith methods.
Why this pattern: This is the trie itself, nothing more. Every other problem in this chapter is this structure with one twist added.
Hint: The only difference between search and startsWith is whether you check the end marker at the final node.
Visual:
flowchart TD
R((root)) --> A((a))
A --> P1((p))
P1 --> P2(("p*"))
P2 --> L((l))
L --> E(("e*"))
style P2 fill:#c8e6c9
style E fill:#c8e6c9
The green nodes carry the end marker. With only “app” and “apple” stored, searching “app” returns true while searching “ap” returns false, even though both paths exist.
Code:
class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
search(word) {
const node = this._traverse(word);
// The end marker is the only thing that separates a stored
// word from a stored prefix.
return node !== null && node.isEndOfWord;
}
startsWith(prefix) {
return this._traverse(prefix) !== null;
}
_traverse(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
return null;
}
node = node.children.get(char);
}
return node;
}
}The solution is a straight application of the main template. The one decision that matters is the end marker: search checks it, startsWith does not. Test with “app” and “apple” inserted, then search “ap”, “app”, and “apple” to confirm the marker does its job.
Medium Problems
2. Design Add and Search Words Data Structure
LeetCode 211 | Difficulty: Medium
Brief: Design a data structure that supports adding words and searching with wildcards, where “.” matches any single character.
Why this pattern: The trie still holds the words, but search becomes a depth-first recursion. A wildcard position has no fixed child, so every child becomes a candidate branch.
Hint: Write search as a recursive function over (position in the word, current node). At a “.” you loop over all children instead of following one.
Visual:
flowchart TD
A["Search 'b..' against bad, dad, mad"] --> B["'b' matches the b branch"]
B --> C["At '.', every child is a candidate"]
C --> D["'a' leads to a word end"]
D --> E["Return true"]
Code:
class WordDictionary {
constructor() {
this.root = new TrieNode();
}
addWord(word) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
search(word) {
return this._dfs(word, 0, this.root);
}
_dfs(word, index, node) {
if (index === word.length) {
return node.isEndOfWord;
}
const char = word[index];
if (char === '.') {
// A wildcard can match any character, so every child
// branch is worth trying and one success is enough.
for (const child of node.children.values()) {
if (this._dfs(word, index + 1, child)) {
return true;
}
}
return false;
}
if (!node.children.has(char)) {
return false;
}
return this._dfs(word, index + 1, node.children.get(char));
}
}The recursion index replaces the descent loop. When the character is a regular letter, one recursive call follows the single matching child. When it is a wildcard, the loop over children is the branching point, and the recursion either succeeds on the first good branch or exhausts all of them. The end marker check at the base case is unchanged from the plain trie.
Complexity: Add runs in
3. Replace Words
LeetCode 648 | Difficulty: Medium
Brief: Replace each word in a sentence with its shortest root from a given dictionary, if one exists.
Why this pattern: For every sentence word you need the shortest dictionary word that is a prefix of it. That is a trie descent that stops at the first end marker.
Hint: Descend as usual, but stop as soon as the current node carries the end marker. The path you have walked so far is the shortest root, so there is no reason to keep going.
Visual:
flowchart LR
A["the cattle was rattled by the battery"] --> B["cat is a root of cattle"]
B --> C["rat is a root of rattled"]
C --> D["bat is a root of battery"]
D --> E["the cat was rat by the bat"]
Code:
function replaceWords(dictionary, sentence) {
const root = new TrieNode();
for (const word of dictionary) {
let node = root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
return sentence.split(' ').map(word => {
let node = root;
let prefix = '';
for (const char of word) {
// Stop at the first end marker: the shortest root wins,
// and a missing character means no root applies.
if (!node.children.has(char) || node.isEndOfWord) break;
node = node.children.get(char);
prefix += char;
}
return node.isEndOfWord ? prefix : word;
}).join(' ');
}The trick is the break condition. A normal trie descent follows every character of the word. Here the descent stops early at the first end marker, because the problem asks for the shortest root, and the end marker tells you a root exists right now. If a character goes missing before any marker, the word keeps its original form. Notice the check order: the missing-character check comes first, so a word that exactly equals a root still terminates correctly at its own final node.
Complexity: Building the trie costs
4. Longest Word in Dictionary
LeetCode 720 | Difficulty: Medium
Brief: Find the longest word that can be built one character at a time, where every prefix of the word must itself be in the dictionary.
Why this pattern: The “every prefix is a word” requirement is exactly what a trie stores implicitly. A branch may only be followed when every node on it carries the end marker.
Hint: Do a depth-first traversal from the root, but only descend into children whose node is a word end. The longest path you can walk is the answer.
Visual:
flowchart TD
A["w, wo, wor, worl, world"] --> B["Every prefix must be a stored word"]
B --> C["w, wo, wor, worl all carry the end marker"]
C --> D["world extends the chain to length 5"]
Code:
function longestWord(words) {
const root = new TrieNode();
for (const word of words) {
let node = root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
node.word = word;
}
let result = '';
function dfs(node) {
// Children in sorted order make ties resolve to the
// lexicographically smallest word of equal length.
const chars = [...node.children.keys()].sort();
for (const char of chars) {
const child = node.children.get(char);
// Only end-marker nodes can extend the chain, because
// every prefix must itself be buildable.
if (child.isEndOfWord) {
if (child.word.length > result.length) {
result = child.word;
}
dfs(child);
}
}
}
dfs(root);
return result;
}The end marker stops being a flag and becomes a gate. A child node can only extend the running answer if it carries the marker, because a word whose own prefix is missing from the dictionary is not buildable one character at a time. Storing the full word on each end node saves you from rebuilding it during the walk. The sorted child order handles the tie-break: when two candidates share the longest length, the first one visited, which is lexicographically smallest, wins.
Complexity: Building the trie and walking it both cost
5. Implement Magic Dictionary
LeetCode 676 | Difficulty: Medium
Brief: Build a dictionary from a word list, then answer whether a search word can be changed into a dictionary word by replacing exactly one character.
Why this pattern: The trie stores the dictionary, and the search becomes a DFS with a budget. You may take one mismatched branch anywhere along the descent, and after that every step must match.
Hint: Carry a boolean through the recursion that records whether the single allowed mismatch has been spent. A word that matches perfectly must return false, because exactly one change is required.
Visual:
flowchart TD
A["Search 'hhllo' against hello, hallo"] --> B["'h' matches at the root"]
B --> C["'h' against 'e': first mismatch, allowed once"]
C --> D["l, l, o all match"]
D --> E["Exactly one change, return true"]
Code:
class MagicDictionary {
constructor() {
this.root = new TrieNode();
}
buildDict(dictionary) {
for (const word of dictionary) {
let node = this.root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
}
search(searchWord) {
return this._dfs(searchWord, 0, this.root, false);
}
_dfs(word, index, node, usedMismatch) {
if (index === word.length) {
// A stored word found with zero mismatches is not an
// answer, because exactly one change is required.
return node.isEndOfWord && usedMismatch;
}
const char = word[index];
for (const [candidate, child] of node.children) {
if (candidate === char) {
if (this._dfs(word, index + 1, child, usedMismatch)) {
return true;
}
} else if (!usedMismatch) {
// Spend the single mismatch here and continue
// straight, since no more are allowed.
if (this._dfs(word, index + 1, child, true)) {
return true;
}
}
}
return false;
}
}This is the wildcard search from problem 2 with one difference: instead of branching freely at every position, you may branch once and then only descend. The boolean carries that rule. The base case does double duty: it rejects words that match perfectly, which is the detail most people miss. The first example on LeetCode, searching “hello” against a dictionary that contains “hello”, returns false, and the usedMismatch flag is the reason.
Complexity: Building the dictionary costs
Hard Problems
6. Word Search II
LeetCode 212 | Difficulty: Hard
Brief: Find every word from a dictionary that appears in a character grid, where words can be formed by adjacent cells moving in four directions.
Why this pattern: A naive grid search restarts from scratch for every dictionary word. Building the trie once lets a single DFS over the grid test every word at once, and branches that cannot lead to any word die immediately.
Hint: Store the full word on the end node instead of a boolean. During the grid DFS, a child that carries a word is a found answer, and the visited marker doubles as a rejection for cells no stored word uses.
Visual:
flowchart TD
A["DFS from every board cell"] --> B{"Cell is a child of the current trie node?"}
B -->|"Yes"| C["Advance in both grid and trie"]
C --> D{"Node carries a complete word?"}
D -->|"Yes"| E["Record the word"]
D -->|"No"| F["Try the four neighbors"]
B -->|"No"| G["Backtrack to the next cell"]
Code:
function findWords(board, words) {
const root = new TrieNode();
for (const word of words) {
let node = root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
// Storing the full word on the final node avoids rebuilding
// it while walking the grid.
node.word = word;
}
const result = new Set();
const rows = board.length;
const cols = board[0].length;
function dfs(i, j, node) {
if (i < 0 || i >= rows || j < 0 || j >= cols) return;
const char = board[i][j];
// The '#' marker means the cell is on the current path,
// and a cell no trie child uses cannot be part of a word.
if (char === '#' || !node.children.has(char)) return;
const next = node.children.get(char);
if (next.word) {
result.add(next.word);
}
board[i][j] = '#';
dfs(i + 1, j, next);
dfs(i - 1, j, next);
dfs(i, j + 1, next);
dfs(i, j - 1, next);
board[i][j] = char;
}
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
dfs(i, j, root);
}
}
return [...result];
}Two patterns work together here. The trie prunes the search: a cell whose character is not a child of the current node cannot lead to any dictionary word, so the recursion stops instead of exploring a dead region of the grid. The grid backtracking keeps the path honest, marking cells with ‘#’ during descent and restoring them on the way out. The set handles duplicates, because the same word can be spelled out from more than one starting cell. The full word stored on the end node means you never have to reassemble it from the path.
Complexity: Building the trie costs
7. Concatenated Words
LeetCode 472 | Difficulty: Hard
Brief: Find every word in a list that can be formed by concatenating two or more other words from the same list.
Why this pattern: Each word must split into shorter words that are all in the dictionary. The trie answers “does this suffix start with a dictionary word” in one descent, and a depth-first search over split points puts the pieces together.
Hint: Sort the words by length and check each word against the trie before inserting it. That way every word a candidate could be built from is already present, and a word can never be used to build itself. Memoize failed states, because the split search re-explores the same positions many times.
Visual:
flowchart TD
A["Sort words by length"] --> B["Check each word against words already in the trie"]
B --> C{"Splits into 2 or more trie words?"}
C -->|"Yes"| D["Add to the answer"]
C -->|"No"| E["Insert the word into the trie"]
D --> E
Code:
function findConcatenatedWords(words) {
const root = new TrieNode();
const result = [];
const canForm = (word, start, node, started, failed) => {
// failed maps a position to the set of nodes that led to a
// dead end, so the same split is not explored twice.
if (started) {
const seen = failed.get(start);
if (seen && seen.has(node)) return false;
}
if (start === word.length) {
// started means at least one shorter word was used, so
// the final segment makes this a real concatenation.
return node.isEndOfWord && started;
}
// A dictionary word ends here. Count it and restart the
// matching of the next character from the root.
if (node.isEndOfWord && canForm(word, start, root, true, failed)) {
return true;
}
const char = word[start];
if (!node.children.has(char)) {
if (started) {
if (!failed.has(start)) failed.set(start, new Set());
failed.get(start).add(node);
}
return false;
}
const ok = canForm(word, start + 1, node.children.get(char), started, failed);
if (!ok && started) {
if (!failed.has(start)) failed.set(start, new Set());
failed.get(start).add(node);
}
return ok;
};
words.sort((a, b) => a.length - b.length);
for (const word of words) {
if (word.length === 0) continue;
if (canForm(word, 0, root, false, new Map())) {
result.push(word);
}
let node = root;
for (const char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
return result;
}The ordering trick does most of the work. Sorting by length means every word that could build a candidate is already in the trie when the candidate is checked, and checking before inserting means a word can never be used to form itself. Inside canForm, the recursion has two moves at every end marker: count the completed word and restart from the root, or keep descending the current path. The started flag records whether at least one word has been used, which is what separates a true concatenation from a plain dictionary word. The memoization stores dead-end states, because without it the split search revisits the same position and node over and over.
Complexity: Sorting costs
These seven problems cover the full range of trie techniques. Start with the plain structure in Implement Trie, add recursion with the wildcard search, use the trie as a helper in Replace Words, and finish with the two Hard problems that combine the trie with backtracking and with dynamic programming. By the end, you should recognize a prefix problem at sight and know which template variation fits it.