Predictive Text / Autocomplete using a Trie (Prefix Tree) Data Structure in Javascript — Part 1

In this article, I will walk you through how to create the “brains” behind a basic autocomplete feature like this:

…using a data structure like this:

If you look at the diagram above, we are essentially creating a tree data structure. The root node is “empty” and has child nodes representing the first letter of “words” stored in our Trie data structure. Each subsequent child is another letter in the “word” until you reach the end of a word represented by “#”. You can see that both words “THERE” and “TAVERN” share a starting letter “T”. Also, the word “THE” is represented as a subset of “THERE” by indicating a “#” on the first “E”.

To begin, let’s create a class for a typical node in our Trie.

Every node can contain any subsequent letter which will be a key in children. Value will represent the letter of the current node. Next let’s create a class for our Root node which will also contain our Trie methods.

Our addWord method essentially looks at each character in the string and checks to see if that node has been created yet. If not, we create a node for that character. Then at the end of the string, we set the endWord property. Next, lets create a method to predict words - that is to say, given a string of characters, return all words in our tree that begin with that string.

We have two helper functions in our predictWord method. getRemainingTree returns the subtree after walking through the input string. For instance, in the top example, an input string of “i” should return the subtree which contains “in” and “is”. allWordsHelper will, given a subtree, return an array of all words in that subtree. logAllWords is a convenience method to log all words in the Trie by calling predictWord on an empty string.

This is just one implementation method for Tries. In the next part of this tutorial, I will expand on this implementation to handle people names and rankings.