Implementing a Trie in JavaScript Part 1
A trie is a tree data structure that is useful for searching and retrieving data. Most often used with strings, where each character of the string is a single node in the tree, which will then have a child node that is the following character of the string. In this blog I will explain how to insert into a trie, and how to determine if a word is in the trie. In the following blog post, I will talk about how to remove a word from the trie, and how to find all the words that begin with a certain prefix in the trie.
Above is a picture of a simple trie. The building blocks of a trie are nodes. The first node is empty, and just serves as the root, every other node represents a letter of a word. The nodes will have a value, and point to the node(s) after them, as well as having a boolean value to determine if they are the end of a word (represented by the asterisks in the picture).
Code
We will start by making our Node class.
It has a value which is merely the letter that it represents, a map called children which contains its children, and endOfWord which is a boolean value that determines whether it is the last letter of a word.
Now we need to start our Trie class.
From here all of the code will go inside this class. You can see our trie starts with an empty Node as the root.
We need to be able to insert a word into our trie.
First we check to make sure the string wasn’t empty, if it was we return false. From there we start at the root, and if root node doesn’t have the first letter of the word, we add it into the children map of the root node. If it does have it, we assign currNode to that node in the trie. We repeat this process until we get to the end of the word, then we set endOfWord to true and return the node.
Now that we can insert a word, we need to be able to determine if the trie has a word.
A similar process to adding a word. We have the option to supply a starting node that is not the root, this comes in handy if you’re using a trie for autocomplete. As someone is typing a word, you don’t want to start from the very beginning of the word each time they type another letter, so being able to supply a different starting node is useful. From there, you go through each letter of the word, if currNode doesn’t have that letter as one of its children, return false. At the end we check to make sure that the last node that currNode was set to, is the end of a word. This is a true or false value, so we just return.
In Conclusion…
These methods are very simple to implement, but don’t expose the real usefulness of using a trie. Removing a word from a trie can be somewhat tricky, as you have to make sure that you are not removing nodes that lead to other words in the trie. A trie really comes in handy when being used as a prefix tree, which I will cover in my next blog!
