Prefix queries and autocomplete

Why this matters

Autocomplete is the best-known use of a trie. You type a few letters and the screen shows suggestions. The trie jumps straight to the node for the letters you typed, then gathers only the words that live under that node. It never looks at words that do not match. That is why autocomplete feels instant even with a dictionary of hundreds of thousands of words.

This lesson turns the walk from lesson one into a list. You will learn how to collect every word under a node, why the output comes out in alphabetical order without any sorting step, how to stop early when you only need the first few suggestions, and how to write the same search without recursion. Each of these ideas appears in interview questions about tries, so each one gets a worked example you can run.

The idea in two steps

Listing the words for a prefix is a two-step job.

1. Walk down the prefix, one letter per step, exactly as startsWith does in lesson one. If a road is missing, there are no matches. Stop and return an empty list. If the walk succeeds, you have reached the node that stands for the prefix.
2. From that node, search everything below it, and collect every node whose flag says a word ends there.

The first step costs O(P), where P is the length of the prefix. The second step visits only the nodes below the prefix. Nodes for other beginnings are never touched. This is the whole reason the structure is efficient for autocomplete: the work is spent on the words that match, not on the whole dictionary.

Think of a library's card catalogue. You go to the drawer labelled "ca", then you read only the cards in that drawer and in the drawers under it. You never open the drawer for "dog". The trie is the catalogue, and the walk is opening the right drawer.

Searching a tree: depth first, from first principles

The second step needs a way to visit every node below a starting node. The usual method for this is a depth-first search, usually called DFS. DFS goes as deep as it can along one road, then backs up to the last place it had a choice, and takes the next road. The name says it: it dives deep first.

Picture a maze with corridors and junctions. A DFS explorer walks down the first corridor from a junction until it reaches a dead end. Then it walks back to the most recent junction and tries the next unexplored corridor. It keeps a note of where it has been so it does not walk the same corridor twice. A trie has no loops, so the explorer never needs to recheck a junction. Each node is reached by exactly one path.

For a trie, a DFS from a node looks like this in words.

• Look at the current node. If its flag says a word ends here, record the word.
• For each child, from the letter 'a' to the letter 'z', go down into that child and repeat.
• When all children are done, return to the parent.

Two details make this work. First, the search has to know the word it is building. Each time you go down a child, you add that child's letter to a growing string. When you come back up, you remove the letter. This add-then-undo pattern is called backtracking. The name comes from the idea that the search backs up along the path it took. Second, the children must be visited in a fixed order. Visiting 'a' to 'z' is what makes the output alphabetical.

The picture below numbers the nodes in the order a depth-first search visits them for the words car, card, care, cat, dog and do. Follow the numbers: the search goes all the way down the c branch before it touches the d branch, and a word's own node is numbered before the longer words below it.

Trie for car, card, care, cat, dog and do, with each node marked by the order a depth-first search visits it

The recursion, step by step

The DFS is naturally written as a recursive function, a function that calls itself on each child. Recursion is easy to misread, so trace it once in detail. Each call handles one node. The call stack is the list of calls that are currently running, and the newest call sits on the top.

The Viz below shows a recursive walk on a binary tree. Each box is one call. Watch how the calls stack up as the walk goes deeper, then unwind as each one finishes.

Notice what the animation shows about the stack. A call waits on the stack while the calls it made are still running. A call disappears only when everything it started has finished. The trie DFS has the same shape. The call for the node "car" waits while the calls for "card" and "care" run, then it returns to its parent.

The function below is the core of autocomplete. It takes a node, the string built so far, and the output list.

void collect(Node* n, string& path, vector<string>& out) {
    if (n->isEnd) out.push_back(path);
    for (int i = 0; i < 26; i++) {
        if (n->next[i]) {
            path.push_back('a' + i);
            collect(n->next[i], path, out);
            path.pop_back();
        }
    }
}

Read it as a list of decisions for one node.

• if (n->isEnd) out.push_back(path); records the word if this node ends one. The current path is exactly the letters from the root to this node, which is the word.
• The loop tries each slot from 0 to 25, which is 'a' to 'z'. Because the loop goes in order, smaller letters are visited first.
• path.push_back('a' + i); adds the letter of the child to the path. The expression 'a' + i turns slot 2 into the character 'c'.
• collect(n->next[i], path, out); searches the child. The path now holds the child's letters, so the child's word is correct.
• path.pop_back(); removes the letter again. After this line, path is the string for the node that called us. That is the backtracking step, and forgetting it is the most common bug in this lesson.

The string& path parameter uses an ampersand, which means the function gets the same string object as its caller, not a copy. Every call adds and removes letters in the same string. This saves copying the whole string at each step, which would be slow for long words.

Worked example 1: the complete autocomplete demo

The next program stores six words, asks for the words under two prefixes, and then asks for a prefix that is not in the trie. It is a complete program, so the Run button can execute it directly.

Output:

car
card
care
--
do
dog
--
0

Trace the first call, autocomplete(root, "car"). The walk goes root, c, a, r, and reaches the r node. The path is initialised to "car", so every word the search collects starts with those letters.

collect runs on the r node. Its flag is true, because "car" was inserted, so "car" goes into out first. Then the loop finds one child, d. The path becomes "card". collect runs on the d node. Its flag is true, so "card" goes into out. The d node has no children, so the call returns and pop_back removes the d, leaving "car". Back in the r node, the loop finds the child e. The path becomes "care", and the e node's flag is true, so "care" is added. The e node has no children, so it returns, the path goes back to "car", and the r node finishes. Output: car, card, care.

Notice why "car" comes before "card". The node for car is a word end, so the search records it before it goes deeper. A shorter word always comes before the longer words that extend it. This is the same rule a dictionary follows.

Now the call autocomplete(root, "d"). The walk reaches the d node under the root, which exists because "dog" and "do" were inserted. The d node itself is not a word, so nothing is recorded there. Its children are o. The o node is a word end, because "do" was inserted, so "do" is recorded. Then the search goes into g, then the word "dog" is recorded. Output: do, dog. The order is correct again, because o comes before g in the alphabet and a word end is recorded before deeper words.

The last call uses the prefix "x". The walk fails at the first step, because the root has no child for x. autocomplete returns an empty list, and size() prints 0. The program never calls collect at all. A missing prefix costs only the walk.

Why alphabetical order comes for free

A common interview question asks why the output is sorted. The answer is in the loop. The loop visits slot 0, then 1, and so on up to 25. Each slot is one letter, so the children of any node are visited in letter order. Within the children of one node, every word in the earlier child's subtree comes before every word in a later child's subtree, because they differ at that letter and the earlier letter is smaller.

Put it in one sentence for an interviewer: the trie stores words by their letters, and visiting the letters in order visits the words in dictionary order. No sort step is needed, and the cost is the same as the search itself.

There is one subtlety. The word at a node comes before any word below it, because the node's own word is shorter. That is why "car" is output before "card". If you record the word after visiting the children, the output would be wrong for prefixes: "card" would come before "car". The position of the if line matters.

Worked example 2: the top k suggestions from input

Autocomplete does not show every match. A search box shows a handful, often five or ten. The next program reads a list of words, then a prefix and a number k, and prints at most k matches. The collect function gets a new parameter, limit, and stops as soon as it has that many words.

Type this as input:

6
car card care cat dog do
car 2

The first line gives the word count. The next line holds six words. The last line gives the prefix and the limit. Input is read as tokens, so spaces and line breaks both separate values.

Output for that input:

car
card

Trace the early stop. The walk reaches the car node, and collect starts there with out empty and limit 2. The first check, out.size() >= limit, is false because 0 is less than 2. The car node is a word end, so "car" goes into out, which now holds one word. The loop goes to child d. The check at the top of the next call is still false, because one is less than two. The card node is a word end, so "card" goes into out, which now holds two words. When the call returns to the loop of the car node, the loop condition out.size() < limit is false, so the loop stops. The search never visits the e child, so "care" is never looked at.

The early stop matters for speed. Suppose a prefix matches a hundred thousand words, and the box shows five. Without the stop, the search would visit all hundred thousand words and throw most away. With the stop, it visits only as many nodes as it needs to find five words, plus the nodes on the way down. Some nodes can be skipped entirely.

Try a missing prefix. If the prefix is "x", findNode returns null, out stays empty, and the program prints none. The return 0 after printing none ends the program early, which is the simplest way to exit a branch in main.

Notice the check if ((int)out.size() >= limit) return; at the top of collect. It is needed because a call can be made when the list is already full. Without it, a call could add one more word before the loop checks the limit. The cast (int) is needed because size() returns an unsigned type, and comparing it directly with an int produces a warning in some compilers.

Worked example 3: sorting words with a trie

A trie can also sort strings. Insert every word, then list them by collecting from the root. The result is sorted alphabetically, and any duplicate words are merged, because each word is stored once. This is a classic interview variant, sometimes called a trie sort, and it runs in time proportional to the total number of letters.

Type this as input:

5
banana apple cherry apple app

The second apple is a duplicate. The program should print each distinct word once, in order.

Output:

app
apple
banana
cherry

Trace the sort. The inserts create the nodes for banana, apple, cherry and app. The second "apple" walks the existing nodes and sets an already-set flag, so no new word appears. The collect starts at the root with an empty path and a limit equal to n, which is 5. That is enough room, because there are at most four distinct words. The root is not a word. The root's children are a, b and c. The a subtree holds "app" and "apple". "app" comes first, because its node is a word end and the search records it before going deeper. Then comes banana under b, then cherry under c.

The limit is set to n for a simple reason. The number of distinct words can never be more than the number of words read. Setting the limit to n means the collect stops only when it has produced every word. It is a safe upper bound.

The same idea sorts any list of strings in O(total letters) time. A comparison sort such as std::sort takes O(n log n) comparisons, and each comparison may read several letters. For long lists of words with many shared prefixes, the trie can be faster. For short lists of numbers, the trie does not apply at all.

Worked example 4: the same search without recursion

Recursion is the clearest way to write a DFS, but it has a cost. Each call uses memory on the call stack, and a very deep trie, such as a word of 100,000 letters, could exhaust the stack. An iterative version uses an explicit stack, which is a container you manage yourself. Interviewers often ask for this version, because it shows you understand what the recursion does.

The idea is to store pairs of a node and its path in a vector used as a stack. The newest entry is at the back. Each step removes the newest entry, records its word if it has one, and pushes its children. The subtle part is the order of pushing. A stack returns the last item pushed first, so to visit 'a' before 'z' we push 'z' first and 'a' last.

Type this as input:

6
car card care cat dog do
ca

Output:

car
card
care
cat

Trace the first three pops. The stack starts with one entry: the ca node and the string "ca". The pop takes it. The ca node is not a word end, so nothing is printed. The loop pushes its two children, t (index 19) and r (index 17). Because the loop goes from 25 down to 0, it pushes t first and r second, so r is on top. The next pop takes "car" from r. The r node is a word end, so "car" is printed. Its children are d (index 3) and e (index 4). The loop pushes e first and d second, so d is on top. The next pop takes "card". It is a word end, so it is printed. It has no children. The next pop takes "care" and prints it. The last pop takes "cat" and prints it. The stack is empty, so the loop ends.

The printed order is car, card, care, cat. It is the same as the recursive version, because a node is printed when it is popped, before any of its children are popped, and children come off the stack in letter order.

The explicit stack holds a copy of each path string, rather than sharing one string as the recursive version does. That is simpler to read, and it costs more memory, because each entry holds its own string. This is a trade-off you can name in an interview. The recursive version uses the call stack and one shared string. The iterative version uses a heap-allocated stack and a string per entry.

The line auto [node, path] = stack.back(); uses a structured binding, a C++17 feature that unpacks a pair into two names. The auto without an ampersand copies the pair, which is what we want, because we pop the entry from the stack right after.

What happens inside the search

To see the work, count the calls and the visits in a trie holding car, card, care, cat, dog and do. The recursive collect starting at the root visits every node exactly once. The root has children c and d. Under c there is a, then r, then d and e. Under the root there is also d, o and g. Counting the nodes, with the root included, gives 10. Each node makes one call, so the search performs 10 calls, and each call runs its loop of 26 slots.

This tells you the cost of autocomplete from the root. It is proportional to the number of nodes in the subtree, times the cost of the loop per node. With a fixed alphabet of 26, the loop costs a constant amount per node. The total is O(number of nodes in the subtree), and in practice O(total letters of the matching words), because each node in the subtree is on the path of at least one matching word.

The loop over 26 slots is the expensive part for sparse nodes. A node with only one child still checks all 26 slots. Real systems sometimes replace the array with a list of children for this reason, as lesson one discussed. The effect is small for a 26-letter alphabet, but a sparse trie of long words can waste time on empty slots.

Complexity

Let P be the length of the prefix and let M be the total number of letters in the matching words.

• Walk to the prefix node: O(P) time.
• Collect all matches: O(M) time, where each node below the prefix is visited once. The loop adds a constant factor of 26 per node.
• Collect the first k matches: the walk is O(P). The search stops after k words, so the time depends on how many nodes it visits before finding k words. In a bad case it may visit many empty branches first. Say so when you answer an interview question.
• Space: the output list holds the matches. The recursion uses one stack frame per level, so the depth is the length of the longest match.

A good answer to "how fast is autocomplete" names the two parts: the walk to the prefix, which depends only on the prefix length, and the collection, which depends on the number of matches or on k. The second part is what limits, which is why systems cap the number of suggestions.

Ranking suggestions by popularity

Alphabetical order is rarely what a user wants. A search box usually ranks suggestions by how often a word is searched or used. This extension is a common interview follow-up, and it needs one new field and one new idea.

Add an integer count to each node. When a word is inserted, increase the count on its final node. Then the count of a word is the value on its word-end node. To find the top k, you must visit every match under the prefix, because a rare word might be a leaf deep in the trie with a high count. Collect the pairs of word and count, then keep the best k with a heap, which is a structure that gives the largest or smallest item quickly.

The cost grows. You can no longer stop early after k words, because the first k words found may not be the most popular. A common improvement is to store, at each node, the best word below it, so the search can prune branches that cannot beat the current top k. That changes the design, so decide which property you need before you start.

State this trade-off out loud in an interview. Alphabetical top k is cheap and simple. Popularity top k is more useful and more costly, and the cost comes from having to look at all matches.

Common mistakes and the messages they produce

Mistake 1: forgetting path.pop_back()

If the path is never shortened, letters pile up. For the input car, card, care, the output becomes car, then card, then cardcare or similar wrong strings, because each later branch starts with the letters of the previous one. The fix is the pop_back after the recursive call. Every push_back before a recursive call needs its matching pop_back after it.

Mistake 2: starting the path empty

If autocomplete calls collect with an empty path instead of the prefix, the output contains only the endings. For the prefix "car", you would print "" and "d" and "e" for card and care. Initialise path to the prefix, as the demo does.

Mistake 3: recording a word after the children

If you move the isEnd check after the loop, prefixes come out in the wrong order. For the words car and card, you would print card before car. The check must happen before the loop, so a word is recorded before any longer word that extends it.

Mistake 4: no check for a null start node

If the walk does not return early for a missing prefix, collect is called with a null pointer, and the first line if (n->isEnd) crashes. The compiler does not warn about this. The sanitizer reports it as a null read, with a line such as SEGV on unknown address near zero and a hint that the address points to the zero page. Check the walk result before calling collect.

Mistake 5: passing a temporary string by reference

If you call collect(root, prefix + "x", out), the new string is a temporary value, which cannot be bound to the string& parameter. g++ reports an error that starts like this, and the rest of the line repeats the type with its full library name:

error: cannot bind non-const lvalue reference of type 'std::string&' ... to an rvalue of type 'std::string'

The fix is to store the string in a named variable first, such as string path = prefix;, and pass that variable. Named values are lvalues, which can be bound to a reference.

Mistake 6: a recursion with no stopping rule

If collect has no base case, the calls never stop. With the sanitizer, the report is a stack overflow, such as ERROR: AddressSanitizer: stack-overflow. Without the sanitizer the program crashes with a segmentation fault. Every recursive function on a trie needs a clear stop, which here is the loop running out of children.

Debugging walkthrough: the wrong words appear

Suppose you call autocomplete(root, "ca") and get car and cardcare. The output is close, which hints at a path bug, not a walk bug. Work through the steps.

Step 1: check the walk. Print the node pointer returned by the walk and its isEnd flag. If the walk reached the right node, the problem is in collect.

Step 2: print the path at each call. Add cerr << "visit " << path << "\n"; at the top of collect. The standard error stream prints to the terminal even when the answers go elsewhere. The output shows the path as each call starts. For the bug above, you would see the path grow from "car" to "carde" without a matching shorten.

Step 3: find the missing pop_back. In the bug, the loop pushes a letter and calls collect, but the code after the call is missing. Restoring the pop_back line fixes it.

Step 4: confirm with a small test. Use the input car, card, care and the prefix "car". The expected output is car, card, care. If the output is correct now, remove the debug print so it does not slow the search.

Keep the habit of printing the path. Strings that grow or shrink wrongly are the most common trie bug, and a single print shows the problem faster than any amount of reasoning in your head.

Variations and edge cases

• The prefix is a word and has no children. The walk ends at a leaf. collect records the prefix once and stops. For "dog" with no longer words, the output is just "dog".
• The prefix is a word and has children. The prefix word comes first, then longer words. For "do" the output is "do" then "dog".
• The prefix is missing. The walk fails and the output is empty.
• The empty prefix. The walk returns the root, so the search lists every word in alphabetical order. For a large dictionary this is slow and rarely useful. A real system caps the output.
• k is zero or negative. With k equal to 0, the first check in collect returns at once and nothing is printed. Decide whether a negative k is an error, and handle it before the search.
• Duplicate words in the input. A trie stores each word once, so duplicates do not appear twice. If the task asks for counts, add a counter to the node instead.
• Words that differ only by case. The code above accepts only lowercase letters, as lesson one explained. Normalise the input first.

Interview and real-world uses

The patterns in this lesson answer many interview questions.

• Autocomplete from a prefix, with a limit of k suggestions. The walk plus a DFS with a stop is the expected answer.
• Sorting a list of strings with a trie, which the worked example shows.
• Counting words with a prefix. Lesson three shows the constant-time method using a pass count, which avoids the search entirely.
• Listing matches as a streaming process, where a generator yields words one at a time. The iterative DFS in worked example 4 is the starting point for that design.

In real systems, autocomplete combines a trie with ranking, caching of common prefixes, and rules for typos. The trie is one part of a larger system. In an interview, say which part you are solving and what you are leaving out.

Practice

Try each exercise before you open the solution. Exercises 1 to 3 are small changes to the code above. Exercises 4 to 6 ask you to reason about the output. Exercises 7 to 10 build something new.

1. Change the first demo so autocomplete returns at most 2 words. Predict the output for the prefix "car" before you run it.

2. Write int countWithPrefix(Node* root, const string& p) that counts the words with prefix p without building a list. Use recursion.

int countBelow(Node* n) {
    if (!n) return 0;
    int total = n->isEnd ? 1 : 0;
    for (Node* child : n->next) total += countBelow(child);
    return total;
}

3. Modify the iterative DFS so it prints words in reverse alphabetical order. Hint: change the direction of the pushing loop.

4. Given the words cart, care, cat and carp, what is the output of collect starting at the node for "car"? Explain each step.

5. Explain why autocomplete returns the empty list before calling collect when the walk fails, and what would happen without that check.

6. A user types the prefix "do" and the trie holds "do", "dog" and "dot". List the output in order and say which node is recorded first.

7. Add a count field to each node and make insert increase it on the word-end node. Write int popularity(Node* root, const string& w) that returns the count for a stored word, or 0 if the word is missing.

8. Write a function that returns the longest word under a prefix node, using alphabetical order to break ties. Hint: compare lengths as you collect.

9. The iterative DFS copies a string for every entry. Explain how you would reduce the copying, and what the cost would be.

10. Write a function vector<string> allWords(Node* root) that returns every stored word in alphabetical order. Use collect with no limit.

What you now know

• Autocomplete walks down the prefix, then runs a depth-first search below that node.
• Backtracking adds a letter before a child call and removes it after, so the path string stays right.
• Visiting the children from 'a' to 'z' produces alphabetical output without a sort.
• A word is recorded before its children, which keeps shorter words first.
• A limit stops the search early, and an explicit stack replaces the recursion when depth is a concern.
• Ranking by popularity needs a count on each node and costs more, because you must see every match.

The next lesson adds counts that answer prefix questions in one walk, and shows how to delete a word without breaking the words that share its letters.