How to effortlessly implement an autocomplete data structure in JavaScript (Using a Trie).

Have you ever wondered how Google knows the next word or sentence you will type in the search bar? Oh yes! they have good algorithms and have collected enough data and everybody knows that. But at the core of such user-friendly features in most of the search bars lies a very powerful yet data structure called a Trie. A Trie (Keyword Tree) is a tree data structure that stores strings and can be used in machine learning, web crawling, and most commonly, the autocomplete feature which we shall implement right away.

How to implement a Trie for autocomplete

Before we get into the implementation, I assume you are familiar with;-

• JavaScript Objects and how to manipulate them
• JavaScript Data Structures and basic methods
• Basic knowledge and terminologies of a tree data structure

Once you are sure of those three, we can delve into this without much strain (I’ve also tried making the code blocks ‘dirty’ with comments for easy interpretation).

There are two important things we are going to consider in this whole implementation;

• the node
• Trie Structure

1. The node

Since a Trie is a tree data structure, it obviously must have a node. Each node represents a letter of any word that will be stored in the Trie. As of our implementation, the node will track the current letter, previous letter, next letters, position (whether it is the last node or not), and a function that joins all the previous letters before that node (to form a word if possible).

implementation of Node properties and methods

from the illustration above, it will have no previous letters on creating a new node since it is a root node (first node in the tree), and no preceding letters until we add words. We then create the getword() method inside the TrieNode object

getWord method

finally, our complete node will look like the one in the illustration below

Complete TrieNode object

The Trie Implementation

After we have created the node structure of our tree, we can now implement the Trie. To achieve our basic autocomplete task, we shall have one property and three methods;-

• root this property will create the first node of the tree
• insert ; this method will create or insert a new word in our Trie ‘dictionary’.
• contains ; this method will check if a word exists in our ‘dictionary’.
• find ; this method will use prefixes to predict words that can be formed with the given prefix. (the words must be available in the dictionary of course.)

Trie Tree implementation with property and methods

We start with the insert method since we cannot make use of the Trie when it lacks a ‘dictionary’

insert method

from the above illustration, iterating through each letter gives us the ability to create a node for each letter. Also, since our nextLetters property is an object, there are various ways we can access the values of the keys (in this case the letters) and I opted for nextLetters[current_letter] . To explain how we are accessing the next letters a little further, here is a snippet.

If the word I am going to insert is cat , we iterate through each letter singly as 'c' , 'a' , and 't' . The object for these letters will look like this;

nextLetters = { 
  c: 'c',
  a: 'a',
  t: 't'
}

to access the letter 'a' and make any comparisons or effects to it, we can say;

nextLetters.a  // return 'a'
OR
nextLetters[a] // returns 'a' if we use a loop

So basically that is how we are trying to access and manipulate letters in the above methods and the next two methods.

Next, we implement the contains method that checks whether a word exists

contains method

If a word exists, it will return true, otherwise false. We can use this method to confirm if our words were inserted into the ‘dictionary’.

And lastly find , the method that makes the whole basic importance of this Trie Data structure. The find method has two parts. First, we check our prefixes and move the node to the last letter of the prefix. If the prefix is exerc , we must make sure our current node is c because it will be used as a reference. This is how we do it.

find method

The findAllWords() the function will be a recursive function that will use the current node of the prefix as a reference point to traverse all the children of that node and then return an array with all the possible words.

findAllWords function

Basically, the function takes in two arguments, the node and and array . First, it checks whether the node represents the last letter of a word. If it is, it will be used by the getword() function the get the corresponding word which will be pushed to the array list of possible words. If it's not, we use a for...in loop to traverse through the node's children so that we access the next node and build the word recursively.

Once all child nodes are visited, the find method will return an array of possible words. And then our Trie will be done. To make some tests, we can implement a trie and do some sampling.

trie tests

So that’s it. you can find the complete code here. If this was helpful don’t forget the claps.