Trie problems and trade-offs

Why this matters

Interviewers rarely ask "build a trie". They describe a problem in which many strings share beginnings, or in which a grid holds letters and you must find many words. The trie is the tool that makes those problems simple. Knowing the shape of the problem, and recognising when a trie fits, is the skill this lesson trains.

This lesson works through four patterns. The first is longest common prefix, where you walk down a single road as long as the road does not split. The second is searching a grid for many words at once, where one depth-first search follows the grid and the trie together. The third is shortest unique prefix, where pass counts from lesson three give the answer in one pass. The fourth is maximum XOR, where a trie over bits finds the best partner for each number. After the four patterns, the lesson compares tries with hash sets, with numbers you can check yourself.

Pattern 1: longest common prefix

The longest common prefix (often called LCP) of a list of strings is the longest beginning that every string shares. For "flower", "flow" and "flight", the answer is "fl", because all three start with f and l, but the next letters differ: o in flower, o in flow, and i in flight. The "o" and "i" differ, so the common part stops at "fl".

Think of the trie as a set of roads. Every word is a road from the root. Walk down from the root. As long as the current node has exactly one child, every word that goes through this node goes to that same child. So every word agrees on that letter. The first node with two or more children is a split, where the words disagree. The first node that is a word end is also a stop, because one word ends there and cannot continue.

So the algorithm is short.

1. Insert every word into a trie. Track, at each node, how many children it has.
2. Start at the root. While the node has exactly one child and is not the end of a word, follow that child and add its letter to the answer.
3. Return the answer.

The trie is not the only way to solve LCP. Sorting the list and comparing the first and last words gives the same answer, and that method is simpler to write. The trie earns its place when the same structure must answer other questions too, or when you add words over time. Mention both in an interview, and pick the trie when the problem asks for more.

The code for this pattern tracks the number of children at each node. A child count is one integer per node. It rises by one whenever a new child is created.

void insert(Node* root, const string& w) {
    Node* cur = root;
    for (char c : w) {
        int i = c - 'a';
        if (!cur->next[i]) {
            cur->next[i] = new Node();
            cur->kids++;
        }
        cur = cur->next[i];
    }
    cur->isEnd = true;
}

The loop that finds the answer is the heart of the pattern.

string res;
Node* cur = root;
while (cur->kids == 1 && !cur->isEnd) {
    for (int i = 0; i < 26; i++) {
        if (cur->next[i]) {
            res.push_back('a' + i);
            cur = cur->next[i];
            break;
        }
    }
}
return res;

The inner loop finds the one child. It is a search over 26 slots, so each step costs 26 checks. That is a constant, so the walk is O(S), where S is the total number of letters in the answer. Each step checks the child count and the flag, then moves.

Worked example: three words

Take the input flower, flow, flight. Insert the words. The root has one child, f, so it has kids 1. The f node has one child, l, so kids 1. The l node has two children, o from flower and flow, and i from flight, so kids 2.

Now walk. The root has one child and is not a word end, so the walk moves to f and adds f to the answer. The f node has one child and is not a word end, so the walk moves to l and adds l. The l node has two children, so the loop stops. The answer is "fl".

Worked example: a single word

Take the input "interview" by itself. Each node on its path has exactly one child, so the walk goes on. At the last letter the node is the end of the word. The loop checks the flag and stops. The answer is "interview", which is correct, because the longest common prefix of a single string is the string itself.

Worked example: no common letters

Take dog and car. The root has two children, d and c, so the loop stops at the start. The answer is the empty string. The output then needs a decision: print nothing, or print a marker. The program in this lesson prints "none" for the empty answer, because a blank line is easy to miss when you read output.

Worked example: a word that is a prefix of the rest

Take "same" and "same" again, or take "fl" and "flower". With "fl" and "flower", the walk reaches the l node, which is a word end because "fl" was inserted. The loop stops there. The answer is "fl", which is correct, because "fl" is a prefix of "flower".

The program below runs the four cases above. It is a complete program, so the Run button can execute it.

Output:

fl
none
interview
same

Each output line matches one trace above. The test list is hard-coded so you can run it without typing. The result for is "same", because the duplicate word sets the same flag twice without creating extra nodes.

Common errors in this pattern are about the stop rule. If you forget the isEnd check, the walk for goes past the end of "fl" and returns "flo", which is wrong. If you forget the kids == 1 check, the walk runs into the split and picks the first branch. Both errors are silent: they print a wrong answer and no message.

Pattern 2: searching a grid for many words

The second pattern is a classic. You are given a grid of letters and a list of dictionary words. You must find every word that can be spelled by moving from cell to cell, up, down, left or right, without using any cell twice in the same word. This is the core of word games such as Boggle.

The naive approach searches for each word separately. For each word, try each cell as a start, then search the four neighbours, and so on. With n words and a grid of R by C cells, that repeats the same grid search n times. Many words share their first letters, so the same cells are explored again and again.

The trie approach does one search of the grid and uses the trie to decide which paths are worth taking. Put all the words in a trie. Start a depth-first search from every cell, and move in the grid and in the trie together. Each step moves to a neighbouring cell and to the child of the current trie node for that cell's letter. If the trie has no such child, no word starts with that path, so the search stops at once. This cuts most of the grid search.

The Viz below shows a depth-first search over a graph. A grid is a graph where each cell is a vertex and each neighbour is an edge. Watch how the search goes deep along one path, backs up, and tries the next neighbour. The grid search does the same thing, except that each step must also match the trie.

Two details keep the search correct.

• A cell cannot be reused on the same path. The code marks the cell with # while it is on the path, and restores the letter when it backs up. The mark stops the search from walking back to the cell it just left.
• A word must be reported once. When a path reaches the end of a word, the code records it and clears the word-end flag, so another path that spells the same word finds no flag and does not record it again.

The picture below shows the grid used in the worked example, with the two found paths drawn on it.

A 4 by 4 letter grid with the paths for oath and eat highlighted by their cell order

The code

The function below is the whole search. It is the same shape as the depth-first search from lesson two, with a grid check at each step.

void dfs(int r, int c, Node* node, string& path, vector<string>& found) {
    if (r < 0 || c < 0 || r >= R || c >= C) return;
    char ch = grid[r][c];
    if (ch == '#') return;  // this cell is already used by the current path
    Node* nxt = node->next[ch - 'a'];
    if (!nxt) return;       // no stored word goes this way
    path.push_back(ch);
    if (nxt->isEnd) {
        found.push_back(path);
        nxt->isEnd = false; // report each word once
    }
    grid[r][c] = '#';
    dfs(r + 1, c, nxt, path, found);
    dfs(r - 1, c, nxt, path, found);
    dfs(r, c + 1, nxt, path, found);
    dfs(r, c - 1, nxt, path, found);
    grid[r][c] = ch;        // restore the cell on the way back
    path.pop_back();
}

Read the function as a list of checks, in order.

• The bounds check comes first. Any cell outside the grid stops the call, so the code never reads outside the grid.
• The # check stops a path from reusing a cell that the current path already holds.
• The trie check stops the search when no word continues this way. This is the step that makes the trie useful. A grid search with no trie would keep going, even when the letters could never form a word.
• The flag check records a word and clears its flag, so it is reported once.
• The four calls explore the neighbours. The order does not change the result, only the order of the output.
• The restore lines undo the # mark and the path letter, so the next search from another start cell sees the original grid.

Worked example: finding oath and eat

The grid in the worked example is four rows of four letters: oaan, etae, ihkr and iflv. The dictionary is oath, pea, eat and rain.

Start the search at each cell in row order. Start at the top left, which holds o. The root has a child for o, because oath is stored, so the search moves there and adds o to the path. The cell's neighbours are a to the right and e below. The o node has the child a, so the search moves right to the a cell and adds a. The a cell at row zero, column one has neighbours o, a, t below it. The a node in the trie has the child t, which matches the cell below, so the search moves down to the t cell at row one, column one.

The t node has the child h, which matches the cell below, at row two, column one. The h node is a word end, because oath is stored. The search records oath and clears the flag. Then it tries the four neighbours of the h cell, but none of them spells a continuation in the trie. It backs up, restoring each cell, and the search continues from the other start cells.

For eat, the search starts at the cell with e in row one, column three. The root has a child for e, because eat and pea are stored, so the search moves there. The e cell's neighbours include the a cell at row one, column two. The e node has child a, which matches. The a cell has the t cell at row one, column one as a neighbour, and the a node has child t. The t node is a word end, so the search records eat.

The other two words, pea and rain, are not found. The search for p never starts, because the grid has no p. The search for rain starts at r in row two, column three. Its neighbours are e above, v below, and k to the left. The trie node for r has child a, but the grid has no a next to r, so the search stops. Both results are correct, and the output is:

oath
eat

The search order matters for the output order. Starting cells are visited in row order, so the word that starts higher in the grid is found first.

The program below runs this exact grid and dictionary. It is complete, so the Run button can execute it directly.

Output:

oath
eat

Why the trie makes this faster

Consider how much work the search skips. For each start cell, the search tries at most four neighbours at each step. Without the trie, a search for every word would try all those paths for each word. The trie merges the paths of all words into one tree, and the search follows one path for each grid route. A route that the trie does not support ends at once.

A common bound for this search is about 4 times 3 to the power of L minus 1 steps for each start cell when L is the word length, because after the first step each new cell has at most three new neighbours. The trie check prunes most of those paths, because very few routes spell a prefix of a stored word. In practice, the trie cost is much less than the bound.

Two notes about this code. It changes the trie: clearing isEnd means you can run the search only once on the same trie. If you need to run it again, rebuild the trie or store the found flags separately. Also, the grid is global, which is convenient for a short program but not a good design for a library. An interviewer may ask you to pass the grid as a parameter.

Complexity for the grid search

Let R and C be the grid size, and let S be the total number of letters in the trie.

• Building the trie: O(S) time and space, with the usual memory cost per node.
• Searching: each start cell may explore a number of paths, bounded by the trie. The worst case is O(R times C times 4 times 3 to the power of L) for a single start cell, but the trie cuts it to the paths that spell prefixes of stored words.
• Output: the list of found words. Each word is reported once.

In an interview, name the bound with the trie, and explain why each path stops early when the trie has no child. That reasoning is the answer.

Pattern 3: shortest unique prefix

The third pattern uses pass counts from lesson three. For each word in a list, find the shortest beginning that no other word in the list shares. This is useful for short codes, such as the shortest command a user needs to type to pick one item from a list.

Take the words dog, cat and cow. The first letter d is shared by no other word, so the shortest unique prefix of dog is "d". The first letter c is shared by cat and cow, so cat needs more letters. The prefix "ca" is shared by no other word, so the shortest unique prefix of cat is "ca". Likewise, cow's shortest unique prefix is "co", because "c" is shared, and "co" is not.

The trie gives this answer in one walk per word. Insert all words, adding 1 to the pass of each node on each word's path. The pass of a node counts how many words pass through it. Then, for each word, walk from the root and stop at the first node whose pass is 1. That node is the first point where only this word goes. The letters walked so far are the shortest unique prefix.

Worked example: the trace

Insert dog, cat and cow. The pass of d is 1, because only dog passes through it. The pass of c is 2, because cat and cow pass through it. The pass of a is 1, because only cat passes through it under c. The pass of o is 1, because only cow passes through it under c.

To find the prefix for dog, walk from the root. The first node is d, whose pass is 1, so the walk stops after one letter. The answer is "d". For cat, the first node is c, whose pass is 2, so the walk continues. The next node is a, whose pass is 1, so the walk stops. The answer is "ca". For cow, the first node is c with pass 2, then o with pass 1, so the answer is "co".

The output for the input is shown in the next program. It is complete and runs directly with the input typed in the Input box.

Type this as input:

3
dog cat cow

Output:

d
ca
co

The walk stops at the first node with pass 1. The code assumes that no word is a prefix of another. If "car" and "card" are both in the list, the walk for "car" never reaches a node with pass 1, because the d branch always keeps one more word on the path. The walk then ends at the end of the word, and the program prints the whole word. That is the right answer only if you define the problem so that words are not prefixes of each other. State that assumption in an interview.

Pattern 4: maximum XOR of two numbers

The fourth pattern moves from letters to bits. Every integer is a string of binary digits, each 0 or 1. The XOR operation (written ^ in C++) gives 1 for each bit where the two numbers differ, and 0 where they agree. XOR is large when the two numbers differ in the high bits. For example, 5 is 00101 and 25 is 11001 in five bits. Their XOR is 11100, which is 28.

The problem: given a list of numbers, find two of them whose XOR is as large as possible. The naive way tries every pair, which takes O(n squared) time. A binary trie solves it in about O(n times 30) time, where 30 is the number of bits in each number. The trie has two children per node instead of 26: one child for bit 0 and one for bit 1. This is a binary trie, a trie over bits.

The key step is the query. For a number x, walk down the trie from the highest bit. At each bit, x has some bit b. The best partner has the opposite bit, 1 minus b, because that makes the XOR bit 1. If the trie has a child for the opposite bit, follow it and set that bit in the answer. If not, follow the child for the same bit, which gives 0 in the XOR for that bit. The walk always finds a path, because the number x itself is in the trie if you insert all numbers.

Worked example: the query for 5

Use five-bit numbers so the picture is small. The trie holds 3, 10, 5, 25, 2 and 8. Their five-bit forms are 00011, 01010, 00101, 11001, 00010 and 01000.

Query x = 5, which is 00101. Start at the root. The highest bit of x is 0, so we want a 1 in that position. The trie has 25 with a leading 1, so the child for 1 exists. Follow it and set the top bit of the answer, which gives 16.

Next bit. x has 0 here, so we want 1. The node for 1 has only 25 under it, and 25 is 11001, whose second bit is 1. The child for 1 exists, so follow it. The answer is now 24.

Next bit. x has 1 here, so we want 0. The node has only 25, whose third bit is 0. The child for 0 exists, so follow it, and the answer is now 28.

Next bit. x has 0 here, so we want 1. The node has only 25, whose fourth bit is 0. No child for 1 exists, so follow the child for 0 instead. The answer stays 28.

Last bit. x has 1 here, so we want 0. The node has only 25, whose last bit is 1. No child for 0 exists, so follow the child for 1. The answer stays 28.

The walk found 28, which is 5 XOR 25. Check the other values for x = 5: 5 XOR 3 is 6, 5 XOR 10 is 15, 5 XOR 2 is 7, and 5 XOR 8 is 13. None is larger than 28. The full answer over all pairs is 28, because 25 XOR 2 is 27 and that is the next best.

The code

The program below uses 30 bits, enough for numbers below 2 to the power of 30. It inserts every number, then asks for each number its best partner.

Type this as input:

6
3 10 5 25 2 8

Output:

28

Read the code in three parts. insert walks the bits of x from the highest, creating children as needed, exactly like the letter trie but with two slots. bestXor is the query from the worked example. The res |= 1 << b line sets the bit in the answer when the opposite child exists. The main function inserts every number, then queries each number and keeps the best value.

The query for a number also finds itself, because the number is in the trie. Its XOR with itself is 0, which is never larger than the true best answer when there are two or more numbers, since the best answer is at least 0. So including it does no harm. An interviewer may ask you to explain this, and it is a good point to make.

The cost is O(n times 30) for the whole program, which is O(n) for a fixed bit width. The memory is one node per bit per number at most, so up to 30 times n nodes. Each node has two pointers, which is 16 bytes, much smaller than the 26-slot nodes of the letter trie.

Complexity

• Insert one number: O(B), where B is the number of bits, 30 here.
• Query one number: O(B).
• Whole problem: O(n times B) time.
• Space: O(n times B) nodes in the worst case.

The brute-force method is O(n squared) and fine for a small list. The trie wins when n is large, such as 100,000 numbers, where n squared is ten billion pairs.

Trie or hash set?

The four patterns answer the question "when is a trie better?" The honest answer is that a hash set is better for most exact-match work. Use this table to decide.

A short rule helps in interviews. Choose a hash set when the only question is whether a whole word is present. Choose a trie when prefixes, sorted listing or per-prefix counts matter. Choose a trie when the same structure must answer a grid or bit problem, as the patterns in this lesson show.

What the memory really costs

Put numbers on the trade-off. Take 100,000 words of about eight letters, which is 800,000 letters in total. A hash set stores each word once, so its cost is roughly the words themselves plus bucket overhead, a few megabytes.

A trie with 26 pointers per node costs about 216 bytes for each node. If no words shared a prefix, the trie would have up to 800,000 nodes, which is about 173 MB. Real word lists share many prefixes. A dictionary of English words shares a lot, because many words start with the same few letters, so the real count is far lower. Still, the trie costs more memory per word, and you should say so.

These are the usual ways to reduce the cost.

• Use a map per node (unordered_map<char, Node*>) so each node holds only the children it has. Memory drops for sparse tries, but each step costs more time.
• Use a sorted list of children for small alphabets. Each node stores a short vector of pairs, which is compact and still ordered.
• Use a compressed trie that merges single-child chains into one edge. This removes most of the empty nodes, and it is the design behind many routing tables.

Name the trade-off you chose. The best answer in an interview is not the fastest structure in the abstract. It is the one that matches the queries and the memory limit.

Common mistakes and the messages they produce

Mistake 1: a grid cell not restored

If the code forgets grid[r][c] = ch; on the way back, the cell stays # for later searches. Words that need that cell are then missed. The output is missing words, and there is no message. The fix is the restore line, placed after the four recursive calls, so every path puts back what it took.

Mistake 2: reporting a word twice

If the code forgets to clear the word-end flag, the same word is recorded for every path that spells it. Here the output shows a duplicate line, such as oath printed twice. The fix is nxt->isEnd = false; after recording the word. Be aware that this changes the trie, as mentioned earlier.

Mistake 3: reading outside the grid

If the bounds check is missing or comes after the read, grid[r][c] reads memory beyond the grid. The read might return a letter by chance, which gives a wrong answer that looks plausible. Put the bounds check first. With the address sanitizer on, an out-of-range read is reported with a line such as a heap or stack buffer overflow, and a stack trace that names the line.

Mistake 4: reading the bit from the wrong end

In the XOR code, the loop must go from the highest bit down to bit 0. If it goes from 0 up, the greedy choice is wrong, because the high bits matter most. The answer is then a wrong value, with no message. Check the loop direction with the 5-bit trace in the worked example.

Mistake 5: a missing bit width

If BITS is 20 but the numbers reach 2 to the power of 30, the high bits are ignored. The answer is too small. Choose BITS so that every value fits, and check the largest value in the input.

Mistake 6: stopping the prefix walk at the wrong node

In the shortest unique prefix code, a walk that stops at the end of the word instead of at the first pass-1 node prints the whole word every time. The check cur->pass == 1 is the stop rule. Test it with two words that share a letter.

Mistake 7: using a grid search with a global grid in a test

The program in this lesson keeps the grid global. If you run two tests in one program, the second test sees the first test's changes if the restore did not finish. Pass the grid as a parameter, or copy it before each search.

Debugging walkthrough: the grid misses a word

Suppose the grid search returns oath but not eat, even though eat is in the grid. Work through the steps.

Step 1: check the start cell. Print each start cell and whether the root has a child for its letter. For eat, the start cell is e at row one, column three. If the root's child for e is missing, the trie was built wrong, not the search.

Step 2: print the path as the search goes deeper. Add a line that prints the path string at each call. For eat, you should see e, then ea, then eat. If the path stops at ea, the next cell is blocked or misread.

Step 3: check the blocked cell. Print the grid value at each neighbour. A # left over from an earlier search means a restore was skipped. The earlier path that set # did not reach the restore line, perhaps because of an early return placed between the mark and the restore.

Step 4: check the trie flag. If eat was already found once, its flag is clear, and a second search cannot record it. The output then has one fewer word. Print the flag before the search to see the state.

In this kind of bug, the path print is the key tool. It shows the exact letters the search sees, and it turns a silent wrong answer into a visible one.

Variations and edge cases

• A word longer than the grid. The search can never reach the end, so the word is not found. The code handles it with no special case.
• A word with a letter that the grid lacks. The root or a node has no child for that letter, so the search stops. Again no special case is needed.
• Duplicate words in the dictionary. The trie stores each word once, so the output lists each once.
• A word that is a prefix of another word that is also in the grid. Both are found, because each has its own word-end flag on a different node.
• Single-letter words. The search records them at depth one, so a one-letter dictionary entry is found wherever its letter appears in the grid.
• The number zero in the XOR problem. XOR with zero is the number itself. The answer is 0 only when every pair XORs to zero, which happens when all numbers are equal or there is only one number.
• Negative numbers in the XOR problem. The code above does not handle them. Two's complement bits differ from the examples, and the program needs a different bit width and a sign rule. Say that you would handle them separately.

Interview and real-world uses

The four patterns each answer a common question.

• Longest common prefix. Insert the words and walk while the path has one child and no word ends. An interviewer may also accept the sort-based answer, but the trie is the expected answer when the question asks for more.
• Word search in a grid. Build a trie of the dictionary, then run one depth-first search from each cell, following the trie and the grid together. Explain the restore and the flag clear.
• Shortest unique prefix. Pass counts give the answer in one walk per word.
• Maximum XOR. Build a binary trie and query greedily from the top bit.

Real systems use these patterns too. Routers use compressed binary tries for longest-prefix matching. Spell checkers and search boxes use letter tries. Word games use the grid search. Each real system adds the details this lesson leaves out, such as caching, compression and ranking, but the core structure is the same.

When you answer in an interview, say the pattern first, then the cost, then the code. "This is a prefix problem, so I will build a trie and walk it. The cost is one walk per query, which is the length of the prefix." That sentence signals that you know the structure and why it fits.

Practice

Try each exercise before you open the solution. Exercises 1 to 4 extend the patterns in this lesson. Exercises 5 to 8 ask you to reason about a result. Exercises 9 and 10 build a larger piece.

1. Write a function that returns the shortest word in a trie that starts with a given prefix, breaking ties by alphabetical order. Hint: the first word found by a depth-first search in alphabetical order is the alphabetically smallest word, but it may not be the shortest, so compare lengths as you collect.

string shortestWithPrefix(Node* start, string path) {
    string best;
    bool found = false;
    function<void(Node*, string&)> dfs = [&](Node* n, string& p) {
        if (n->isEnd && (!found || p.size() < best.size())) {
            best = p;
            found = true;
        }
        for (int i = 0; i < 26; i++) {
            if (n->next[i]) {
                p.push_back('a' + i);
                dfs(n->next[i], p);
                p.pop_back();
            }
        }
    };
    dfs(start, path);
    return best;
}

2. Find the longest common prefix of a single-word list where the word is also the prefix of another word in the list. Predict the output for , then check it.

3. Change the grid search so it returns the words sorted alphabetically, not in discovery order. Predict whether the output for the worked example changes.

4. Write a function that counts how many words in the trie start with a vowel-free prefix. This is a trick question. Explain why the trie cannot answer it directly, and what would be needed.

5. Trace the maximum XOR query for x = 8 over the five-bit trie holding 3, 10, 5, 25, 2 and 8. Predict the value and check it against the list.

6. In the shortest unique prefix code, what happens if the words are dog, dot and dog? Explain the output.

7. The binary trie code uses int for the input. Explain what goes wrong if the input has a value of 2 to the power of 31 or more.

8. Explain why the grid search with the # mark does not need a separate visited array, and what a visited array would cost.

9. Write a function int countBits(Node* root) for the binary trie that returns the number of nodes. Explain what the count tells you about memory.

10. Write a program that reads a list of words and prints, for each word, its shortest unique prefix, but treats a word that is a prefix of another word as having no unique prefix. Print "none" in that case.

What you now know

• A longest common prefix walk follows one child at a time and stops at a split or at a word end.
• A grid word search runs one depth-first search, moving in the grid and in the trie together, with a # mark and a restore on the way back.
• Shortest unique prefixes come from pass counts: the first node with pass 1 is the stop.
• Maximum XOR uses a binary trie and a greedy query from the highest bit.
• A trie costs more memory than a hash set, but it answers prefix, order and count questions that a hash set cannot answer in one walk.
• In an interview, name the pattern, the cost, and the memory trade-off before you write the code.

The next lesson asks you to build a small command-driven word index that uses everything in this module.