Trie Data Structure – Insert Search Delete & Print Program with JavaScript

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.
- A value – which might be null
- An array of references to child nodes – Initially this array will contain a null value.
- 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:
- Left Child Node Reference
- Right Child Node Reference
- 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
youtube abone satin al
Simply wish to say your article is as surprising.
The clarity in your post is simply nice and I could assume you are an expert on this subject.
Fine with your permission allow me to grab your feed to keep updated with the forthcoming post. Thanks a million and please keep up the gratifying work.
ucuz takipçi satın al
I visit each day web pages and sites to read articles or reviews, but this website
offers quality-based articles.