Implementing a Trie Data Structure in JavaScript

When working with large sets of data, it can be challenging to find the most efficient way to search and retrieve specific items. One way to optimize your search process is by using a trie data structure. Trie, also known as a prefix tree, is a tree-like data structure that stores data in a way that enables efficient search and retrieval.

In this article, we will explore the basics of trie data structure in JavaScript and how it can help improve the performance of your applications.

What is a Trie Data Structure?

As we’ve said above, a trie is a tree-like data structure that stores data in a way that enables efficient search and retrieval. The word “trie” comes from the word “retrieval,” which is a hint about its intended purpose. Tries are also known as prefix trees because they store data in a way that makes it easy to search for words or other sequences of characters that share a common prefix.

A trie consists of nodes and edges. Each node in the trie represents a single character or a set of characters, and each edge represents a connection between two nodes. The edges in the trie are labeled with characters, and each node represents a prefix of one or more words.

The root node of a trie represents an empty string, and each node below the root represents a prefix of one or more words. The leaf nodes in the trie represent complete words. Tries are often used to store sets of strings or words, but they can also be used to store other types of data.

Implementing a trie in JavaScript

Creating a trie data structure in JavaScript is straightforward. You can use an object to represent each node in the trie, and the keys of the object represent the characters that can be stored in that node. Here’s an example of a basic trie in JavaScript:

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      let char = word[i];
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;

    for (let i = 0; i < word.length; i++) {
      let char = word[i];

      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  startsWith(prefix) {
    let node = this.root;
    for (let i = 0; i < prefix.length; i++) {
      let char = prefix[i];
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }
}

// Optional export
module.exports = Trie;

In this example, we define two classes, TrieNode and Trie, where TrieNode represents each node in the trie, and Trie represents the overall trie data structure. The Trie class has three methods: insert, search, and startsWith.

The insert method is used to insert a new word into the trie. It takes a string as an argument, and it iterates over each character in the string. For each character, it checks if there is a child node with that character. If there is no child node with that character, it creates a new node and adds it as a child of the current node. It then sets the isEndOfWord property to true for the last character in the string to indicate that this node represents the end of a complete word.

The search method is used to search for a specific word in the trie. It takes a string as an argument and iterates over each character in the string. For each character, it checks if there is a child node with that character. If there is no child node with that character, it returns false. If it reaches the end of the string and the isEndOfWord property is set to true for the last node, it returns true.

The startsWithmethod is used to check if a prefix exists in the trie. It takes a string as an argument and iterates over each character in the string. For each character, it checks if there is a child node with that character. If there is no child node with that character, it returns false. If it reaches the end of the string, it returns true.

Using a Trie Data Structure

Tries are useful in a variety of applications, such as autocomplete features, spell checkers, and searching for words in a large corpus of text. One example use case for a trie in JavaScript is to implement an autocomplete feature for a search bar on a website.

Let’s say you have a website that allows users to search for articles. You want to provide autocomplete suggestions as the user types their query. You can use a trie to store all of the possible article titles, and then use the startsWith method to find all of the article titles that start with the user’s query.

Here’s an example of how you could use the trie we defined earlier to implement this feature:

// Import file (optional)
const Trie = require("index.js");

const trie = new Trie();

// insert all of the article titles into the trie
const articleTitles = [
  "JavaScript Basics",
  "Advanced JavaScript Techniques",
  "Introduction to React",
  "Getting Started with Node.js",
];
articleTitles.forEach((title) => trie.insert(title.toLowerCase()));

// search for article titles that start with the user's query
const userInput = "jav";
const suggestions = [];
let node = trie.root;

for (let i = 0; i < userInput.length; i++) {
  const char = userInput[i];
  if (!node.children[char]) {
    break;
  }
  node = node.children[char];
}

if (node.isEndOfWord) {
  suggestions.push(userInput);
}

function findSuggestions(node, prefix) {
  if (node.isEndOfWord) {
    suggestions.push(prefix);
  }
  for (const [char, child] of Object.entries(node.children)) {
    findSuggestions(child, prefix + char);
  }
}

findSuggestions(node, userInput);

console.log(suggestions); // ['javascript basics', 'advanced javascript techniques']

In our example above, we inserted all of the article titles into the trie using the insert method. We then use the startsWith method to find the node in the trie that represents the prefix entered by the user. Afterwards, we use a recursive function called findSuggestions to traverse the trie from the starting node and find all of the complete words that start with the prefix. Also note that we store the suggestions in an array, logging them to the console.

Note: We have exported and imported some things above. This is for your own benefit. If you’d like to experiment with the code, feel free to create a directory, adding an index.js file containing the Trie class (first code block), and another file with whatever name you’d like with the code directly above (second code block).

Conclusion

In this article, we explored the trie data structure. We explored how to implement one, and even checked out a use case. A trie is a powerful tool for efficiently storing and retrieving sets of data. They can be used in a variety of applications and can significantly improve the performance of your applications.

If you enjoyed this article, you might find our other data structure articles useful. Please drop any questions or comments below and leave us a reaction.

Master the coding interview

If you want to explore data structures and algorithms via a video course, taught by an amazing instructor, Andrei Neagoi, Zero to Mastery has a great course for you: Master the Coding Interview: Data Structures + Algorithms.

In this course, you will:

• Ace coding interviews given by some of the top tech companies.
• Learn to implement and use different data structures.
• Learn the notorious Big-O notation.
• Become more confident and prepared for your next coding interview.

Get 10% off by using code FRIENDS10.

FAQ

Q: What is a trie data structure?

A: A trie, also known as a prefix tree, is a data structure used for efficiently storing and retrieving sets of strings. It consists of a tree-like structure where each node represents a single character in a string, and the edges represent the connections between the characters.

Q: What are some common applications of tries?

A: Tries are commonly used in applications where efficient prefix search or autocomplete features are required. They are also used in spell checkers, search engines, and compilers.

Q: How do tries compare to other data structures like arrays and hash tables?

A: Tries are more efficient than arrays and hash tables for prefix search and autocomplete features, as they only need to traverse the nodes that match the prefix. However, arrays and hash tables are generally faster for random access to individual elements.

Q: How do you insert a string into a trie?

A: To insert a string into a trie, you start at the root node and iterate over each character in the string. For each character, you check if a child node with that character exists. If it does, you move to that child node. If it doesn’t, you create a new node with that character and add it as a child of the current node. Once you reach the end of the string, you mark the last node as the end of a complete word.

Q: How do you search for a string in a trie?

A: To search for a string in a trie, you start at the root node and iterate over each character in the string. For each character, you check if a child node with that character exists. If it does, you move to that child node. If it doesn’t, the string is not in the trie. Once you reach the end of the string, you check if the last node is marked as the end of a complete word. If it is, the string is in the trie.

Q: What is the time complexity of trie operations?

A: The time complexity of trie operations depends on the length of the strings being stored and the number of strings. Insertion, search, and deletion operations have a time complexity of O(m), where m is the length of the string. However, the space complexity of a trie can be high, especially for large sets of strings.

Disclosure: We are affiliated with ZTM (Zero to Mastery), so if you happen to be interested in the course above and purchase it through our link, we will recieve a small commission of the sale (at no extra cost to you). Please also note that we have browsed ZTM courses and have found them to be some of the best material on the web. We don’t recommend them solely for personal gain.

Thank you for the support!