What is Trie and How to implement it?

Tech-letter #15 | March 28, 2023

Trie

• A Trie, also known as a Prefix Tree or a Radix Tree, is a tree-based data structure that is often used for efficient string searching and storage.

• It consists of a series of nodes that are connected by edges, where each node represents a character in a string. By traversing the tree from the root node to a leaf node, we can reconstruct a string that corresponds to a unique path in the tree.

• Tries are particularly useful for string operations such as searching for all strings with a given prefix, finding the longest common prefix among a set of strings, or searching for strings that match a certain pattern. They are also useful in applications where a large number of strings need to be stored and searched, such as in a dictionary or autocomplete feature.

• Let us implement the trie step by step

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

  The TrieNode class represents a node in a trie data structure. Each node has two properties:

  • children: This is an object that holds references to the child nodes of the current node. The keys of the object are the characters of the alphabet, and the values are references to the child nodes.

  • isEndOfWord: This is a boolean flag that indicates whether the current node represents the end of a word in the trie. If this flag is set to true, it means that the path from the root node to the current node represents a valid word in the trie.

  Understanding the 'insertWord' Method

      class Trie {
          constructor() {
              this.root = new TrieNode();
          }
          // method 1
          insertWord(word) {
              let currentNode = this.root;
              for (let i = 0; i < word.length; i++) {
                  const char = word[i];
                  if(!currentNode.children[char]) {
                      currentNode.children[char] = new TrieNode();
                  }
                  currentNode = currentNode.children[char];
              }
              currentNode.isEndOfWord = true;
          }
  
          // ....
      }
  

  1. It starts by setting currentNode to the root node of the Trie.

  2. It then iterates through each character in the word string, checking if the character exists as a child node of the currentNode. If the character is not a child node of currentNode, the method creates a new child node for the character and sets it as a child of currentNode.

  3. The method then moves to the child node corresponding to the current character and repeats the above steps until it reaches the end of the word string.

  4. Once it reaches the end of the word string, it sets the isEndOfWord flag of the last node to true, indicating that the path from the root node to the last node represents a valid word in the Trie.

  Understanding the 'searchWord' Method

      searchWord(word) {
          let currentNode = this.root;
          for (let i = 0; i < word.length; i++) {
              const char = word[i];
  
              if (!currentNode.children[char]) {
                  return false;
              }
              currentNode = currentNode.children[char];
          }
          return currentNode.isEndOfWord;
      }
  

  The searchWord method is similar to the insert method. But, instead of inserting it just iterates through each character that the user has input & then it checks that the character is present or not. If the character is not present withing the current node it just returns fale, else it continues through the loop. Once the loop is continued you will get the property isEndOfWord which is returned.

  Understanding the 'startsWith' Method

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

  Event the startsWith method is similar to the other methods. Here, you are returning a boolean. If the entered key matches all the keys that are stored, then the for loop is completed & boolean true is returned. If, a single key from the prefix fails to match then boolean false is returned.

  You can use the following code to test the trie

     const trie = new Trie();
     trie.insert("apple");
     console.log(trie.search("apple"));   // true
     console.log(trie.search("app"));     // false
     console.log(trie.startsWith("app")); // true
     trie.insert("app");
     console.log(trie.search("app"));     // true
  

Building an application using trie

Let’s try to build a simple autocomplete application using trie. This involves all the methods that I have explained above. The only differencethat you notice will be in thesearch method`.

    class Trie {

        // constructor
        // ...

        // All methods same as above
        // ...

        searchWord(word) {
            let currentNode = this.root;
            for (let i = 0; i < word.length; i++) {
                let char = word[i];
    
                if (!currentNode.children[char]) {
                    return [];
                }
                currentNode = currentNode.children[char];
            }
    
            return this.getAllWords(currentNode, word);
        }

        getAllWords(node, prefix) {
            const words = [];
            if (node.isEndOfWord) {
                words.push(prefix)
            }

            for (let child in node.children) {
                words.push(...this.getAllWords(node.children[child], prefix + child));
            }
            return words;
        }
    }

The search method takes a partial word as an argument and returns an array of all possible word completions that start with the given word.

• We start by initializing a currentNode variable to the root of the Trie. We then loop through each character in the word. For each character in the word, we check if the current node has a child node corresponding to that character. If not, it means that there is no word completions that start with the word, so we return an empty array.

• If the empty array is not returned that means the loop continues & ends at a point with a node where isEndOfWord = true. Then we return by calling the getAllWords() method.

Understanding getAllWords() method

let us take an example

   root
   |-- 'a'
   |   |-- 'p'
   |   |    |-- 'p'
   |   |         |-- 'l'
   |   |              |-- 'e'
   |   |                   |-- '*'
   |   |-- 'r'
   |        |-- 'm'
   |             |-- '*'
   |-- 'c'
   |    |-- 'a'
   |         |-- 'r'
   |              |-- '*'
   |-- 't'
        |-- 'e'
             |-- 'a'
                  |-- 'm'
                       |-- '*'

• We start by initializing an empty array of words.

• Since the current node is the root node, we loop through each child node of the root node using a for...in loop.

  a. For the first child node ‘a’, we concatenate the prefix “a” with the character ‘a’ using the + operator. This gives us the updated prefix “aa”.

  b. We call the getAllWords method recursively with the child node ‘a’ and the updated prefix “aa” as arguments. This will return an array of all possible word completions that start from the node ‘a’.

  c. We use the spread operator … to concatenate the resulting array of words with the words array defined earlier. This adds the words found from the node ‘a’ to the list of all possible word completions found so far.

  d. We repeat steps 2-3 for the next child node ‘r’. Once all child nodes have been processed, we return the final words array containing all possible word completions that start from the node ‘a’ or ‘r’.

  e. So in this example, the getAllWords method will return the array [“apple”, “arm”], since these are the two words in the Trie that start with the prefix “a”.