Data Structures in JavaScript: Binary Search Tree


Introduction

Coming from a front end background where most of the stuff is achieved by using a map or a list, I always wanted to explore commonly used data structures in JavaScript.

This is post #1 of the series dedicated to explore commonly used data structures in javascript— explanation and code walk through.

Lets get started with Binary Search Tree

Background

Binary Search Tree is a binary tree where

  • The left sub-tree of a node contains only nodes with keys less than the parent’s node key.
  • The right sub-tree of a node contains only nodes with keys greater than the parent’s node key.
  • The right and left sub-tree should also be a binary search tree.
Fig 1 Binary Search Tree

Fig 1 is a BST where node with key 24 is the root node and all nodes to the left of the node with key 24 is less than 24 and left sub-tree is also a BST. All nodes to the right if the root node is greater than the key of the root node. Enough talking, lets deep dive —

Lets create a class BSTNode to create the node for the binary search tree.

export class BSTNode {
constructor(key, left = null, right = null) {
// the constructor creates the node
this._key = key;
this._left = left;
this._right = right;
}

/* Getter and Setter for key */
get key() { return this._key; }
set key(key) { this._key = key; }
  /* Getter and Setter for left sub tree */
get left() { return this._left; }
set left(left) { this._left = left; }
  /* Getter and Setter for right sub tree */
get right() { return this._right; }
set right(right) { this._right = right; }
}

Lets create a BST class to deal with the binary search tree operations — INSERT, DELETE, LOOKUP and TRAVERSAL. The instance of class BST will have a root property which points to the root node of the BST and is initialized to null. The length property is also assigned to 0.

// Create private properties
const length = Symbol('length');
// Create private methods name
const inOrderTraversal = Symbol('inorder');
const preOrderTraversal = Symbol('preorder');
const postOrderTraversal = Symbol('postorder');
export class BST {

// The newly created BST instance will have length of 0
// and root will be null
constructor() {
this.root = null;
this[length] = 0;
}

// get length of the nodes in BST
get len() {
return this[length];
}
}
// create a BST instance
const bst = new BST();
console.log(bst.root) // null
console.log(bst.len) // 0
}

Insert Operation

To insert a value in the binary search tree

  • Create a new node.
  • Find a place to add a new node. Compare the value to be inserted with the root node. If the value is less than the root node then repeat the same procedure with the left sub-tree and if the value is greater than the root node then repeat the same steps with the right sub-tree.
  • Insert the node

Let’s see this through an example. In order to insert 3 in the BST of fig. 1, first create a node with key 3. Second step is to look for a place to insert the newly created node. Since 3 is less than 24, move to the left sub-tree and compare 3 and 18. 3 is still less than 18, so move towards left sub-tree and compare 3 and 7. 3 is less than 7 and node 7 has no left sub-tree, so this is the place where 3 will be inserted.

Fig. 2 Insert 3 in the BST of Fig. 1

Add insert method to BST class.

/**
* Insert value in the BST
* @param {*} val
*/
insert(val) {
// create a BST node
const bstNode = new BSTNode(val);
/**
* @name recurseBST
* @param {*} node - optional, default value is this.root
*/
const recurseBST = (node = this.root) => {
if (node.key > val && !node.left) {
node.left = bstNode;
this[length]++;
} else if (node.key > val) {
recurseBST(node.left);
} else if (node.key < val && !node.right) {
node.right = bstNode;
this[length]++;
} else if (node.key < val) {
recurseBST(node.right);
}
}
if (!this.root) {
// if the root is null then assign the created node to the root.
this.root = bstNode;
this[length]++;
} else {
recurseBST();
}
}

Insert the element in the binary search tree

bst.insert(3);

Lookup Operation

BST search is similar to insert operation. The element to be searched is compared with the root node. If the value matches then the search is complete and recursion stops. If the searched value is less than the node’s value then repeat the same step with left sub-tree and if the searched value is greater than the node, then repeat the same steps with the right sub-tree.

To search 19 in the BST of fig. 1 —

  • Compare 19 and 24(root node).
  • Since 19 < 24, Move towards left sub-tree and compare 19 and 18
  • Since 19 > 18, Move towards right sub-tree and compare 19 and 19. It’s a match.

Fig. 3 shows the steps involved to search 19 in the BST.

Fig. 3 Find 19 in the binary search tree of Fig. 1

Below is the code snippet to find an element in the BST

/**
* Looks for a value in the BST.
* @param {string|number} val
* @return {object} response
*/
lookup(val) {
let response = { hasVal: false, currentNode: null, parentNode: null };
const lookRecursively = (node = this.root, parent = null) => {
if (node.key === val) {
response.hasVal = true;
response.currentNode = node;
response.parentNode = parent;
} else if (node.left && node.key > val) {
lookRecursively(node.left, node);
} else if (node.right && node.key < val) {
lookRecursively(node.right, node);
}
}
lookRecursively();
return response;
}
//search 19
bst.lookup(19) // {hasValue: true, currentNode: [object Object], parentNode: [object Object]}

Delete Operation

Deletion in BST is fairly complex operation. There are three possible cases to consider —

Case 1: Node to be deleted is a leaf node

First the node to be deleted is searched in the BST. If the node is found and if its a leaf node then simply remove the node. In fig. 4 node 3 is the leaf node (no left and right child), so it can be deleted directly.

Fig. 4 Delete Leaf Node

Case 2: Node to be deleted has only one child

The node to be deleted is looked up in the BST. If the node has just one child (left child or right child), parent of the node is linked directly to the node’s child.

Fig. 5 Delete Node with one child node

Case 3: Node to be deleted has two children

This is the most tricky case. If node to be deleted has two children (left child and right child), then

  • Find the minimum element (successor) from the right sub-tree
  • Replace the value of the node to be deleted with the successor.
  • Remove the minimum element from the right sub-tree.

In Fig. 6, node to be deleted (node 18) has two children. The successor is node 19, since the right sub-tree has just one element. Node 18 is replaced with node 19 and then node 19 is deleted from right sub-tree.

Fig. 6 Delete Node with two child nodes

Code snippet to delete a node from the BST —

delete(val) {
if (!this.root) {
return new Error('BST is empty. Cannot delete from empty BST');
} else {
let findNode = this.lookup(val);
if (findNode.hasVal) {
// case 1
// when the node has no children or when its a leaf
// then simply delete the node
if (!findNode.currentNode.left && !findNode.currentNode.right) {
const direction = findNode.parentNode.key > val ? 'left' : 'right';
findNode.parentNode[direction] = null;
this[length]--;
}
// case 2
// when node has just 1 child
// Simply delete the key and point the parent to the child
else if (!!findNode.currentNode.left ^ !!findNode.currentNode.right) {
const parentToCurNodeDir = findNode.parentNode.key > val ? 'left' : 'right';
const curNodeToChildDir = findNode.currentNode.left ? 'left' : 'right';
findNode.parentNode[parentToCurNodeDir] = findNode.currentNode[curNodeToChildDir];
this[length]--;
}
// case 3
// when node has both left and right children
// Find minimum value in the right subtree of the node containing the key to be deleted.
// Replace the key to be deleted with the min value.
// Then delete the min val from the right subtree.
else if (findNode.currentNode.left && findNode.currentNode.right) {
// find successor
const successor = this.findMin(findNode.currentNode.right);
findNode.currentNode.key = successor.subtree.key;
successor.parent.left = null;
this[length]--;
}
} else {
return new Error('Node not found.');
}
}
}
/**
* Find minimum node of the given subtree.
* If subtree is not passed then
* @param {BST} subtree
* @returns {BST, BST} returns min node and its parent
*/
findMin(subtree = this.root) {
let parent;
while (subtree.left) {
parent = subtree;
subtree = subtree.left;
}
return { subtree, parent };
}
// delete operation
bst.delete(3);
bst.delete(7);
bst.delete(18);

Complexity of BST operations

Comparison table —


I started working on data-structures.js, a library which will provide popular data structures along with Wiki to promote and facilitate usage of data structures in JavaScript(browser based app and node based app). Feel free to contribute.

Stay tuned for more.