Data structures are important in computer programming for organizing, managing, and storing data quickly and efficiently. It’s important for a software engineer to have a good grasp of the various data structures.
This knowledge is useful to help you solve problems during coding interviews and build fast and efficient applications.
Today, we would be looking at some advanced data structures such as segmented trees, tries, self-balancing trees, and binary index trees.
The knowledge of basic data structures like trees, stacks, and heaps, would be a good foundation for this article.
Today, we will be learning:
This course contains a detailed review of all the common data structures and provides implementation level details in JavaScript. Also available in other languages.
Data Structures for Coding Interviews in JavaScript
The word ‘trie’ is derived from the word retrieval. Tries are an ordered tree-like data structure efficient in handling programming problems related to strings.
It is also called a Prefix Tree or a Digital tree.
Tries are used in dictionary word searches, spell-checking and in search engines by making auto-suggestions. Some properties are necessary to maintain the overall efficiency of a trie, they include:
For example, in English, there are 26 letters so the number of unique nodes cannot exceed 26. Likewise, in Bengali with 50 letters would have 50 unique nodes.
Pros
Cons
Enjoying the article? Scroll down to sign up for our free, bi-monthly newsletter.
Every node in a trie represents an alphabet. A typical node in a trie consists of three data members:
char
: This stores the character that the node is supposed to contain.children[ ]
: An array that consists of pointers to children nodes. The size of this array depends on the number of alphabets. All are set to null.isEndWord
: A flag to indicate the end of a word. It is set to false by default and is only updated when words end during insertion.A trie would be implemented using the TrieNode
class, and each node would have at most 26 children if we are storing English words. The root node (usually placed on top) contains 26 pointers, each representing a letter in the English alphabet.
These pointers hold either
null
or anothertrieNode
.
The children pointers have a zero index and all words are stored in a top-to-bottom manner. Remember to always set the isEndWord
flag to true on the last character to indicate the end of the word.
To implement a trie node, create a Trienode.js
file and paste the following code:
"use strict";module.exports = class TrieNode{constructor(char){this.children = [];for(var i=0; i<26; i++){ //Total # of English Alphabetsthis.children[i]=null;}this.isEndWord = false; //will be true if the node represents the end of wordthis.char = char; //To store the value of a particular key}//Function to mark the currentNode as LeafmarkAsLeaf(){this.isEndWord = true;}//Function to unMark the currentNode as LeafunMarkAsLeaf(){this.isEndWord = false;}}
To insert a key(word) into a trie, you first check if the character in the key exists at the index you need it to be. If it does, you set the isEndWord
on the last character to true
.
If a prefix is present, the new key would be added as an extension of the last prefix key. The last case would be if there is no common prefix, the children nodes would be added to the root node which is always null.
The key length determines the trie depth. Note that null keys are not allowed in a trie and all keys are stored in lowercase.
Always remember to set the
isEndWord
value of the last node totrue
.
Create an index.js
file and add the following code to it:
use strict";const TrieNode = require('./TrieNode.js');class Trie{constructor(){this.root = new TrieNode(''); //Root node};getIndex(t){return t.charCodeAt(0) - "a".charCodeAt(0);}//Function to insert a key in the Trieinsert(key){if (key == null){return;};key = key.toLowerCase();let currentNode = this.root;let index = 0;//Store the character index//Iterate the trie with the given character index,//If the index points to null//simply create a TrieNode and go down a levelfor (let level=0; level<key.length; level++){index = this.getIndex(key[level]);if (currentNode.children[index] == null){currentNode.children[index] = new TrieNode(key[level]);console.log(String(key[level]) + " inserted");}currentNode = currentNode.children[index];}//Mark the end character as leaf nodecurrentNode.markAsLeaf();console.log("'" + key + "' inserted");};//Function to search a given key in Triesearch(key){return false;};delete(key){return;}}// Input keys (use only 'a' through 'z' and lower case)let keys = ["the", "a", "there", "answer", "any","by", "bye", "their","abc"];let t = new Trie();console.log("Keys to insert: ");console.log(keys);//Construct Triefor (let i=0; i<keys.length; i++){t.insert(keys[i]);}
In the code above, a Trie class is created. The root node ) is initialized in the constructor. Then, we iterate over characters in the key and get the index for each character using getIndex( )
.
Next, in an insert()
method, we first write a check to ensure that null keys are not allowed and all keys are stored in lower case. Then we store the character’s index by iterating the trie with the given character index.
If the index points to null, we create a TrieNode to go a level down. Finally, we mark the last node as the leaf node, since the word has ended.
For a key with n characters, the worst-case time complexity turns out to be since we need to make iterations.
To search through a trie, you need to take note of three possible cases:
isEndWord
value of the last character on the trie is set to false.search(key){if (key == null){return false; //null key}key = key.toLowerCase();let currentNode = this.root;let index = 0;//Iterate the Trie with given character index,//If it is null at any point then we stop and return false//We will return true only if we reach leafNode and have traversed the//Trie based on the length of the keyfor (var level=0; level<key.length; level++){index = this.getIndex(key[level]);if (currentNode.children[index] == null){return false;}currentNode = currentNode.children[index];}if (currentNode != null && currentNode.isEndWord){return true;}return false;};
Nodes without child branches are easily deleted. The leaf node exists first till the entire word is deleted. For prefixes, the isEndWord
value is set to false.
Words with common prefixes would have their last node deleted along with all parent nodes in the branch that do not have any other children and are not end characters.
To delete a node in a trie, we first write a helper function to check if the currentNode
has any children.
Then we write a recursive function that takes a key, the key’s length, a trie node, and the level (index) of the key as an argument. This function deletes any given key.
//Helper FunctionhasNoChildren(currentNode){for (let i=0; i<currentNode.children.length; i++){if (currentNode.children[i] != null)return false;}return true;}//Recursive functiondeleteHelper(key, currentNode, length, level){let deletedSelf = false;if (currentNode == null){console.log("Key does not exist");return deletedSelf;}//Base Case: If we have reached the node which points to the alphabet at the end of the key.if (level == length){//If there are no nodes ahead of this node in this path//Then we can delete this nodeif (this.hasNoChildren(currentNode)){currentNode = null;deletedSelf = true;}//If there are nodes ahead of currentNode in this path//Then we cannot delete currentNode. We simply unmark this as leafelse{currentNode.unMarkAsLeaf();deletedSelf = false;}}else{let childNode = currentNode.children[this.getIndex(key[level])];let childDeleted = this.deleteHelper(key, childNode, length, level + 1);if (childDeleted){//Making children pointer also None: since child is deletedcurrentNode.children[this.getIndex(key[level])] = null;//If currentNode is leaf node that means currentNode is part of another key//and hence we can not delete this node and it's parent path nodesif (currentNode.isEndWord)deletedSelf = false;//If childNode is deleted but if currentNode has more children then currentNode must be part of another key//So, we cannot delete currentNodeelse if(this.hasNoChildren(currentNode) == false)deletedSelf = false;//Else we can delete currentNodeelse{currentNode = null;deletedSelf = true;}}elsedeletedSelf = false;}return deletedSelf}//Function to delete given key from Triedelete(key){if (this.root == null || key == null){console.log("None key or empty trie error");return;}this.deleteHelper(key, this.root, key.length, 0);}}
Self-Balancing Binary Search Trees are a height-balanced tree that automatically tries to keep its height as minimal as possible when performing basic operations.
A balanced tree is one where for every node, the height of its right and left subtrees differs by at most 1.
The time complexity of all three basic operations- Insertion, deletion, and search take time, where is the height of the Binary Search Tree.
Common examples of Self-Balancing BST include Red-Black Trees, AVL, Splay Tree, and treaps. These BSTs perform Left or Right Rotations after performing insertion and delete operations while maintaining its BTS property.
Get hands-on with data structures without scrubbing through videos or documentation. Educative’s text-based courses are easy to skim and feature live coding environments - making learning quick and efficient.
A segment tree is a tree data structure used in storing intervals or segments. It is used in cases where there are multiple range queries on the array and modifications of elements of the same array.
It follows the principle of a static structure, whereby a structure cannot be modified once it’s built. This means that we can update the values of nodes but we cannot change its structure.
Before building a segment tree, we need to decide the following:
A common case would be finding the sum of all the elements in an array from indices L to R.
Here, at each node (except the leaf nodes), the sum of its children nodes is stored.
A segment tree can be built using recursion (i.e, from the bottom-up). Each leaf represents a single element, and in each step, data from two leaves are used to form an internal parent node.
This parent node can be merged with another leaf or parent node depending on what level it is on, till it gets to the root node.
The merge operation used depends on the question being solved. So, recursion will end up at the root node, which will represent the whole array.
The image below illustrates a sum query for an array:
let x = [2, 6, -3, 8, -5];
The shaded boxes represent the leaf nodes while the clear boxes represent the internal parent nodes.
Segment trees are a flexible data structure. It can be used in solving problems like finding the sum of elements on some segments in an array or finding the minimum query of all elements in an array with indices l
to r
in time.
A binary indexed tree (also known as a Fenwick tree) is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers efficiently.
It provides a way to represent an array of numbers in an array or a tree. The time complexity for every operation on binary index trees is . The tree will take nodes.
Each binary tree node contains an index and a value. The value is a prefix sum.
Compared to segmented trees, binary indexed trees are more space-efficient and relatively easier to implement, especially during programming contests.
I hope that this helped you get a good understanding of some of the more advanced data structures. There’s still so much more to learn about these data structures and others, such as:
You can continue your learning with Educative’s course on Data Structures for Coding Interviews in JavaScript. The course aims to give you a detailed explanation of all common JavaScript data structures.
It also contains real-world data structure problems and their solutions. By the end of the course, you should be better equipped to write better code with all the different data structures that you learn.
Happy learning!
Free Resources