Implement a Trie in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach…

Implement a Trie in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

Tries, also known as prefix trees, are a data structure used for storing and searching for strings in an efficient manner. They are commonly used in applications such as spell checkers and autocomplete features.

The concept behind a trie is to store each character of a string in a separate node, with the root node representing the beginning of the string. Each node also has multiple children, representing the possible next characters in the string. This allows for fast searching and insertion of strings, as the number of nodes needed to reach a string is equal to the length of the string.

In JavaScript, we can implement a trie using objects to represent the nodes. Each node will have a property called “children” which is an object containing the next character as the key and the child node as the value. The node will also have a property called “end” which indicates whether or not the node represents the end of a string.

To insert a string into a trie, we start at the root node and iterate through each character of the string. For each character, we check if the character exists as a child of the current node. If it does, we move to that child. If it does not, we create a new child for that character and move to it. Once we reach the end of the string, we set the “end” property of the current node to true.

To search for a string in a trie, we follow a similar process. We start at the root node and iterate through each character of the string, moving to the child node corresponding to that character. If we reach the end of the string and the “end” property of the current node is true, then the string exists in the trie. If we reach the end of the string and the “end” property is false, or if we reach a node with no child for the next character, then the string does not exist in the trie.

One useful application of a trie is to find all strings in the trie that begin with a certain prefix. To do this, we can perform a search for the prefix and return all strings that are children of the final node reached during the search.

Here is an implementation of a trie in JavaScript:

class TrieNode {
}
 
 
``javascript
class Trie {
this.root = new TrieNode(null);
}
let current = this.root;
for (let i = 0; i < word.length; i++) {
let ch = word[i];
if (!(ch in current.children)) {
current.children[ch] = new TrieNode(ch);
}
search(word) {
let current = this.root;
for (let i = 0; i < word.length; i++) {
let ch = word[i];
if (!(ch in current.children)) {
return false;
}
return current.isEnd;
}
startsWith(prefix) {
let current = this.root;
for (let i = 0; i < prefix.length; i++) {
let ch = prefix[i];
if (!(ch in current.children)) {
return false;
}
return true;
}
For example:
 
trie.insert("car");
trie.insert("bat");
console.log(trie.search("car")); // true
console.log(trie.search("bat")); // true
console.log(trie.search("cab")); // false
 
console.log(trie.startsWith("ba")); // true
console.log(trie.startsWith("c")); // true
console.log(trie.startsWith("b")); // true
console.log(trie.startsWith("d")); // falseTries are a useful data structure for storing and searching for strings in an efficient manner. They are commonly used in applications such as spell checkers and autocomplete features and can be easily implemented in JavaScript using objects to represent the nodes.
 
 
#### JavaScript eBook
 
I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. [Check out the ebook now](https://www.mitrakos.com/ebook)!
 
I founded [Higglo Digital](https://higglo.io) and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a *beautifully designed website*, [check us out](https://higglo.io).
 
I also created [Wanderlust Extension](http://www.wanderlustapp.io/) to discover the most beautiful places across the world with highly curated content. Check it out!