Trie Data Structure in JavaScript

💡 A Trie is a kind of tree, known by many names including prefix tree, digital search tree, and retrieval tree (hence the name 'trie').

A trie represents a sequence in its structure. It stores sequences of values rather than individual single values.
It can have multiple child nodes where Binary Tree only has a maximum of two children.
Words and strings can be retrieved from the structure by traversing down a branch path of the tree.
Each trie has an empty root node, with references to other nodes. Each node of a trie can have as many as 26 references (Based on English alphabets).

✔ We’ll notice that a single node in a trie contains the below things.

1. A value – which might be null
2. An array of references to child nodes – Initially this array will contain a null value.
3. Word End boolean value – that represents the ending of a word or not by using true or false.

Nodes in a trie do not store an entire string or word instead it saves a character or a part of that string as a key. By traversing from the root node to the leaf node, we can build a string from these small parts of the key.

💡 Trie is also called the N-ary tree because it allows us to have n number of children of a particular node.

✋Real-world example

✔ A real-world example of Trie we can see in AutoComplete feature. In every search engine like Google, we see the first search field where we type a char and it gives us top suggestions, which is created with Trie data structure.
✔ Another real example is String matching where tries are used a lot.

********************************

Let’s Start writing Programs in JavaScript

💻 First Create a Node Class

let Node = function () {
  this.keys = new Map(); // This is JS Map to store value and child nodes 
  this.wordEnd = false; // Boolean value
  this.setEnd = function (value) {  //set wordEnd value
    this.wordEnd = value;
  };
  this.isEnd = function () { // get WordEnd value
    return this.wordEnd;
  };
};

💻 Create a Trie Class First – Simply create a class using the function keyword in javascript and then we will add all required methods like insert, delete, exists, and print using prototype.

let Trie = function () {
  this.root = new Node();
};

💡 Insertion

Trie.prototype.insert = function (input) {
  // Get root node
  let node = this.root;
  // loop on all characters of input string
  for (let i = 0; i < input.length; i++) {
    // check if char exists or not
    if (!node.keys.has(input[i])) {
      // if not exists than create new Node
      let temp = new Node();
      // assigning this new Node as Value and char as key in Map
      node.keys.set(input[i], temp);
      // now marked this newly created node temp to origional node
      node = temp;
    } else {
      // if char exists than get its child Node and assign that in node variable
      node = node.keys.get(input[i]);
    }
  }
  //finally set end true after for loop end
  node.setEnd(true);
  console.log(this.root);
};

💡 Search – Create a method to check a string exists

Trie.prototype.isExists = function (word) {
  // get root node
  let node = this.root;
  // loop over all chars of word
  for (let i = 0; i < word.length; i++) {
    // If char exists than get its child node and assign this in node variable
    if (node.keys.has(word[i])) {
      node = node.keys.get(word[i]);
    } else {
      // if char does not exists than return false
      return false;
    }
  }
  return node.isEnd(); // will return true or false
};

💡 Delete Word

To check a word exists or not in Trie, we traverse from the Root node to Leaf Node by using for loop on words each character and at last node, we check wordEnd value. If its value is true means that string exists and if its value is false means that word is not present in Trie.

wordEnd = true - String exists
wordEnd = false - String does not exist

So Delete a node in Trie – we simply mark the leaf node as false.

Trie.prototype.delete = function (word) {
  let node = this.root;
  for (let i = 0; i < word.length; i++) {
    if (node.keys.has(word[i])) {
      node = node.keys.get(word[i]);
    } else {
      return false;
    }
  }
  // Delete from Trie - means set WordEnd value as false
  node.setEnd(false);
  return true;
};

💡 Print all words in an array

Trie.prototype.printAllWords = function () {
  // create an array to store all string
  let words = [];
  // get root Node
  let node = this.root;

  // recursive call of this search for every child node to build a string
  let search = function (node, str) {
    // for-of loop on every key entries
    for (const entry of node.keys.entries()) {
      let char = entry[0]; // get char as Key
      node = entry[1]; // get its child node

      // if node wordEnd value is true
      if (node.isEnd()) {
        // concat char into str and push into words array
        words.push(str.concat(char));
      }
      // call search for child node
      search(node, str.concat(char));
    }
  };
  search(node, ""); // initial search calling
  return words;
};

💻 ****Run Program****

const myTrie = new Trie();
myTrie.insert("Jan");
myTrie.insert("Feb");
myTrie.insert("March");
myTrie.insert("Apr");
myTrie.insert("May");
myTrie.insert("Jun");
myTrie.insert("Jul");

console.log(myTrie.printAllWords());

console.log("deleted Feb", myTrie.delete("Feb"));
console.log("deleted May", myTrie.delete("May"));
console.log("Exists Feb", myTrie.isExists("Feb"));
console.log("Exists May", myTrie.isExists("May"));
console.log("Exists Apr", myTrie.isExists("Apr"));
console.log("Exists Dec", myTrie.isExists("Dec"));

console.log(myTrie.printAllWords());

***Output***

Node {keys: Map(1), wordEnd: false, setEnd: ƒ, isEnd: ƒ}
Node {keys: Map(2), wordEnd: false, setEnd: ƒ, isEnd: ƒ}
Node {keys: Map(3), wordEnd: false, setEnd: ƒ, isEnd: ƒ}
Node {keys: Map(4), wordEnd: false, setEnd: ƒ, isEnd: ƒ}
Node {keys: Map(4), wordEnd: false, setEnd: ƒ, isEnd: ƒ}
Node {keys: Map(4), wordEnd: false, setEnd: ƒ, isEnd: ƒ}
Node {keys: Map(4), wordEnd: false, setEnd: ƒ, isEnd: ƒ}

 (7) ["Jan", "Jun", "Jul", "Feb", "March", "May", "Apr"]

 deleted Feb true
 deleted May true
 Exists Feb false
 Exists May false
 Exists Apr true
 Exists Dec false

 (5) ["Jan", "Jun", "Jul", "March", "Apr"]

💡 Explore a Node to see its structure

✋ Time and Space Complexity of Trie

The Time complexity of creating a trie is O(n * l), where n is the number of words, and l is the average length of the word.

In Trie data structure, the time complexity for insertion, search, and deletion of a word is O(n) where n is word length.

Space Complexity of Trie data structure is O(n * m * c) where n is the total number of words or strings, m is the maximum length of string and c is the alphabet’s size.

Above Complete Code is written based in JavaScript Map Class. So now let’s write code using simple Objects.

💡 Trie in JavaScript with using simple Object to store Child Nodes

See below Node structure with simple children object to store child nodes.

/* Trie Data Structure Program using JavaScript
*/

let Node = function () {
  this.endWord = false; // word end here
  this.children = {}; // This is simple object to store all child nodes
};

let Trie = function () {
  this.root = new Node();

  this.insert = function (input) {
    let node = this.root;
    for (let i = 0; i < input.length; i++) {
      if (!node.children.hasOwnProperty(input[i])) {
        let temp = new Node(); // creating new Node
        node.children[input[i]] = temp; 
        node = temp;
      } else {
        node = node.children[input[i]];
      }
    }
    node.endWord = true; // finally set end true
    console.log(this.root);
  };

  this.isExists = (word) => {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      if (node.children.hasOwnProperty(word[i])) {
        node = node.children[word[i]];
      } else {
        return false;
      }
    }
    return node.endWord; // will return true or false
  };

  this.delete = (word) => {
    let node = this.root;
    for (let i = 0; i < word.length; i++) {
      if (node.children.hasOwnProperty(word[i])) {
        node = node.children[word[i]];
      } else {
        return false;
      }
    }
    node.endWord = false;
    return true;
  };

  this.printAllWords = () => {
    let words = [];
    let node = this.root;

    let search = function (node, str) {
      for (const entry of Object.entries(node.children)) {
        let char = entry[0];
        node = entry[1];

        if (node.endWord) {
          words.push(str.concat(char));
        }
        search(node, str.concat(char));
      }
    };
    search(node, ""); // initial search calling
    return words;
  };
};

const myTrie = new Trie();
myTrie.insert("Jan");
myTrie.insert("Feb");
myTrie.insert("March");
 myTrie.insert("Apr");
 myTrie.insert("May");
myTrie.insert("Jun");
myTrie.insert("Jul");

console.log(myTrie.printAllWords());

console.log("deleted Feb", myTrie.delete("Feb"));
console.log("deleted May", myTrie.delete("May"));
console.log("Exists Feb", myTrie.isExists("Feb"));
console.log("Exists May", myTrie.isExists("May"));
console.log("Exists Apr", myTrie.isExists("Apr"));
console.log("Exists Dec", myTrie.isExists("Dec"));

 console.log(myTrie.printAllWords());

💡 Let’s understand the difference between the Binary tree & Binary Search tree?

A Binary tree is a data structure where every node can have 0, 1, or 2 nodes. Each node will be either Parent Node or Child Node.
There can max two children of a parent node and that is called Left Child and Right Child.

Every Node contains:

1. Left Child Node Reference
2. Right Child Node Reference
3. Data

First Node or Topmost node is called the Root Node.
When a Node has any Child that is called Parent Node.
If any Node that does not contains any child known as Leaf Node.
The node that has at least 2 children known as an internal node.
The longest distance from the topmost node to the leaf node known as the height of the node.
In a Binary tree, there is no order to store data in nodes.

Binary Search Tree is a tree where we store data in some order.
The value of the left child must be smaller than the parent node and the value of the right child must be greater than the parent node.

A binary tree is used to store a collection of comparable items like numbers. It can therefore be used to store a set of numbers or data that can be represented by numbers. BST structure is sorted so it can be searched quickly to find an item.

If a tree has exactly two children for every node and all Leaf nodes are on the same level that called a Perfect Binary Tree.

For more details read here….
https://www.javatpoint.com/binary-tree-vs-binary-search-tree

Trie Data Structure in JavaScript

+2

0