Building Autocomplete

We’re just about ready to build a real autocomplete feature. To make this a tad easier, let’s first build a slightly simpler function that we’ll use to help us with this feature.

Collecting All the Words

The next method we’re going to add to our Trie class is a method that returns an array of all the words in the trie. Now, it’s rare that we’d actually want to list the entire dictionary. However, we’re going to allow this method to accept any node of the trie as an argument so that it can list all the words that start from that node.

The following method, called collect_all_words, collects a list of all the trie’s words starting from a particular node:

This method relies heavily on recursion, so let’s break it down carefully.

The method accepts three primary arguments: words, node, and word.

When we first call this method, we must pass in words as an empty array. As the method proceeds, it will fill this array with words from the trie. The method eventually returns this array once we’ve filled it with all the desired words.

The node argument allows us to specify which node in the trie to start collecting the words from. If we don’t pass in this argument, our method will start from the root node, collecting every word in the entire trie.

The word argument defaults to an empty string. As we move through the trie, we add characters to this word. When we reach a "*", the word is considered complete and we add it to the words array.

Let’s now break down each line of code.

The first thing we do is set the current_node:

By default, the current_node will be the root node, unless we passed in some other node as the method’s first parameter. Let’s assume for now that the current_node is indeed the root node.

Next, we begin a loop that iterates over all the key-value pairs in the current_node’s children hash table:

In each iteration of the loop, the key is always a single-character string, and the value, child_node, is another instance of TrieNode.

Let’s skip to the else clause, as this is where the magic happens:

This line recursively calls the collect_all_words function.

The first argument is the words array. By passing this array along in each recursive call, we’re able to fill it with complete words, effectively building this list as we traverse the trie.

The second argument is the child_node. This allows us to recursively call the collect_all_words method on the child node, continuing to collect all the words from the child node and on.

The third argument is word + key, making it so that as we move through each node of the trie, we add the key to the current word, building up the word as we go.

The base case is when we reach a "*" key, indicating we’ve completed a word. At this point, we can add the word to the words array:

At the end of the function, we return the words array. If we called this function without passing in a specific node, this will return the complete list of words in the trie.

Recursion Walk-Through

Let’s run through a quick visual example of this using a simple trie. This trie holds two words, “can” and “cat”:

Call 1: In the very first call of collect_all_words, the current_node starts out at the root, word is an empty string, and the words array is empty:

We iterate over the root node’s children. The root node happens to only have one child key, the "c", which points to a child node. Before we recursively call collect_all_words on this child node, we need to add the current call to the call stack.

We then recursively call collect_all_words on the "c" child node. We also pass in word + key as the word argument. word + key is the string "c", since word was empty and the key is "c". And we also pass in the words array, which is still empty. The next image shows where we are once we make this recursive call:

Call 2: We iterate over the current node’s children. It has just one child key, the "a". Before recursively calling collect_all_words on the respective child node, we’ll add the current call to the call stack. In the diagram that follows, we call this current node the "a" node, meaning it’s the node that has "a" as a child.

We then recursively call collect_all_words. We pass in the child node, "ca" (which is word + key), and the still-empty words array:

Call 3: We iterate over the current node’s children, which are "n" and "t". We’ll start with the "n". Before making any recursive calls, though, we need to first add the current call to our call stack. In the diagram that follows, we call this current node the "n/t" node, meaning it’s the node that has both "n" and "t" as children.

When we then call collect_all_words on the "n" child, we also pass in "can" as the word argument as well as the empty words array:

Call 4: We iterate over the current node’s children. In this case, it has only one child, which is the "*". This is our base case. We add the current word, which is "can", to the words array:

Call 5: We now pop the top call from our call stack, which was the call of collect_all_words on the node with the children keys of "n" and "t", and where word was "ca". This means we now return to that call (as we return to whatever call we pop from the call stack):

Here we can make a subtle but important point. In the current call, word is back to "ca", since that was the word argument when we first initiated this call. However, the words array now contains the word "can" even though the array was empty when we originally made this call.

Here’s the reason why this works. In many programming languages, an array can be passed up and down a call stack because the array remains the same object in memory even when we add new values to it. (The same concept applies to hash tables as well, which was how we were able to pass it along as part of the memoization technique we looked at in Chapter 12, .)

When a string is modified, on the other hand, the computer creates a new string instead of truly modifying the original string object. Therefore, when we updated word by changing it from "ca" to "can", the previous call still only has access to the original string, "ca". (In some languages, this may work slightly differently. For our purposes, though, this is the general idea.)

In any case, we’re in the middle of a call where words contains the word "can", and word is "ca".

Call 6: At this point, we’ve already iterated over the "n" key, so the loop is now up to the "t" key. Before recursively calling collect_all_words on the "t" child node, we need to add the current call to the call stack again. (This will be the second time we add this call to the call stack. We previously popped it off, but now we’re going to add it again.)

When we call collect_all_words on the "t" child, we pass in "cat" as the word argument (since that is word + key) and the words array:

Call 7: We iterate over the current node’s children. The only child here is "*", so we add the current word of "cat" to our words array:

At this point, we can unwind the call stack, popping off each call and completing its execution, each of which ends by returning the words array. The final call we complete—which was the first call to kick this all off—returns words as well. Because this contains the strings "can" and "cat", we’ve successfully returned the trie’s entire word list.