Binary Tree JavaScript

Introduction to Binary Tree JavaScript

In this article, we will see how we can implement the binary search tree in JavaScript language with the help of an example. All the steps and functions are provided with comments to understand what we are doing at each step.

How to Implement BST?

We can do that by using the following functions:

• addNewData(data) – To add new value to tree.
• deleteExistingData(data) – To delete any existing node of the tree.
• findMininumValue() – Retrieve the minimum value node from BST.
• retrieveRootValue() – Fetch the value of root node.
• inorderTraversal(node) – Traverse the tree in inorder format.
• preorderTraversal(node) – Traverse the tree in preorder format.
• postorderTraversal(node) – Traverse the tree in postorder format.
• find(node, data) – Search for a particular node in the tree.

Examples

Below is the example mentioned :

Code:

class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryST
{
constructor()
{
// root of a binary seach tree
this.root = null;
}
}
// subsidiary method that will help to create a new node and add data to it
addNewData(data)
{
// Creating a new node with the data to be stored being initialised in it
var newNode = new Node(data);
// In case if the root value is null then a new node is inserted and made as the root of tree
if(this.root === null)
this.root = newNode;
else
// Find the appropriate location inside the tree and add a ew node in that place
this.addNewDataNode(this.root, newNode);
}
// This method will add the new data at the appropriate position in the tree
addNewDataNode(node, newNode)
{
// In case if the newly added data is having smaller value it is moved to the left side of the tree
if(newNode.data < node.data)
{
// In case if the left node is empty that is null then the new data node is added there
if(node.left === null)
node.left = newNode;
else
/* If no left node having null value found call the same method
recursively until null node is found at left side*/
this.addNewDataNode(node.left, newNode);
}
// In case if the newly added data is having larger value than node it is moved to the right side of the tree
else
{
// In case if the right node is empty that is null then the new data node is added there
if(node.right === null)
node.right = newNode;
else
/* If no right node having null value found call the same method
recursively until null node is found at right side*/
this.addNewDataNode(node.right,newNode);
}
}
// subsidiary method which makes a call to delete the required node from the tree
deleteExistingData(data)
{
// root is re-initialized with
// root of a modified tree.
this.root = this.deleteExistingDataNode(this.root, data);
}
/* The method which will delete the data present in node of the tree,
if no such node found search for the node in tree and the delete it */
deleteExistingDataNode(node, key)
{
// If root value of the tree is null then return the same
if(node === null)
return null;
// In case if data is having value less than root then move to left subtree
else if(key < node.data)
{
node.left = this.deleteExistingDataNode(node.left, key);
return node;
}
// In case if data is having value greater than root then move to right subtree
else if(key > node.data)
{
node.right = this.deleteExistingDataNode(node.right, key);
return node;
}
// In case if data is having value equal then delete current node
else
{
// Delete the node which does not have children
if(node.left === null && node.right === null)
{
node = null;
return node;
}
// Delete the node which have one child
if(node.left === null)
{
node = node.right;
return node;
}
else if(node.right === null)
{
node = node.left;
return node;
}
// aux will contain the minimum value of the right sub tree after deleting both the children
var aux = this.findMininumValue(node.right);
node.data = aux.data;
node.right = this.deleteExistingDataNode(node.right, aux.data);
return node;
}
}
// Traverse all the nodes of tree in inorder format
inorderTraversal(node)
{
if(node !== null)
{
this.inorderTraversal(node.left);
console.log(node.data);
this.inorderTraversal(node.right);
}
}
// Traverse all the nodes of tree in preorder format
preorderTraversal(node)
{
if(node !== null)
{
console.log(node.data);
this.preorderTraversal(node.left);
this.preorderTraversal(node.right);
}
}
// Traverse all the nodes of tree in postorder format
postorderTraversal(node)
{
if(node !== null)
{
this.postorderTraversal(node.left);
this.postorderTraversal(node.right);
console.log(node.data);
}
}
// Find the node having minimum value in tree starting with current node
findMininumValue(node)
{
// if left of a node is null
// then it must be minimum node
if(node.left === null)
return node;
else
return this.findMininumValue(node.left);
}
// return the value of root node of BST
retrieveRootValue()
{
return this.root;
}
// find particular node with supplied data
find(node, data)
{
// If there is empty tree return null
if(node === null)
return null;
// if data vale is having lesser value than node move to left side
else if(data < node.data)
return this.find(node.left, data);
// if data vale is having greater value than node move to right side
else if(data > node.data)
return this.find(node.right, data);
// if data vale is having equal value asnode return this node
else
return node;
}
// Create a new oject of the class Binary search tree which is BinaryST
var BST = new BinaryST();
// Adding the new node to the binary search tree
BST.addNewData(15);
BST.addNewData( 28);
BST.addNewData(10);
BST.addNewData(7);
BST.addNewData(22);
BST.addNewData(17);
BST.addNewData(13);
BST.addNewData(5);
BST.addNewData(9);
BST.addNewData(30);
var root = BST.retrieveRootValue();
BST.inorderTraversal(root);
// Removing node with no children
BST.deleteExistingData(5);
var root = BST.retrieveRootValue();
// prints 7 9 10 13 15 17 22 28 30
BST.inorderTraversal(root);
// Removing node with one child
BST.deleteExistingData(7)
var root = BST.retrieveRootValue();
// prints 9 10 13 15 17 22 28 30
BST.inorderTraversal(root);
// If node has two children then delete it
BST.deleteExistingData(15);
// 17
// / \
// 10 28
// / \ / \
// 9 13 22 30
var root = BST.retrieveRootValue();
console.log("Tree content when traveled in in order manner");
BST.inorderTraversal(root);
console.log("Tree content when traveled in post order manner");
BST.postorderTraversal(root);
console.log("Tree content when traveled in pre order manner");
BST.preorderTraversal(root);

Output:

Conclusion

We can create a Binary search tree having all the nodes with lesser value on the left side and greater value on the right side by using this programming languages and with the help of many classes and the methods for implementing the same.