JavaScript

How to Calculate Height and Depth of a Node in a Binary Tree Using JavaScript?

8 months ago
by Abdul Moeed
A binary tree consists of multiple nodes, the node at the top is known as the root node, and other nodes that are below in the hierarchy are considered as its child. Each node in a binary tree can have at most two child nodes as from its name binary. The node in the binary tree contains random data which gets preserved for a longer time without any lossage of data.

This guide explains the procedure to calculate the height and depth of a node in a binary tree by covering the below-stated sections:

How to Calculate the Height of a Node in a Binary Tree Using JavaScript?

The binary tree is mostly used in database systems to store single records in the form of nodes. Due to its fast traversal behavior, the database response time also gets improved. The “height” of a node is the distance of a “parent” node from the “leaf” node, it tells the length of a tree or max time interval taken by the binary tree to find a specific node. Let’s visit the below list to understand the procedure of calculating the height of a node in a Binary tree.

Key Points
The procedure to calculate the height of any node available in a binary tree is stated below:

Let’s take a look at the visual representation of the above scenario:

Take a look at the below code block for the practical demonstration of a JavaScript program to calculate the height of a node in the binary tree:

var height = -1;
class Node
{
 constructor()
 {
  this.content = 0;
  this.left = null;
  this.right = null;
 }
};
var setNode = (item) =>
 {
  var tempNode = new Node();
  tempNode.content = item;
  tempNode.left = tempNode.right = null;
  return tempNode;
 }
var heightCalculation = (rootNode, x) =>
{

 if (rootNode == null)
  {
   return -1;
  }
    var leftSide = heightCalculation(rootNode.left, x);
    var rightSide = heightCalculation(rootNode.right, x);

    var result = Math.max(leftSide, rightSide) + 1;
  if (rootNode.content == x)
   {
    height = result;
   }
   return result;
  }

var calcHeight = (rootNode, x) =>
{
    heightCalculation(rootNode, x);
    return height;
}

var rootNode = setNode(3);
rootNode.left = setNode(6);
rootNode.right = setNode(9);
rootNode.left.left = setNode(12);
rootNode.left.right = setNode(15);
rootNode.left.right.right = setNode(24);
rootNode.right.left = setNode(18);
rootNode.right.right = setNode(21);
var k = 3;

document.write("Height of a Provided Binary Tree: " + calcHeight(rootNode, k));

The description of the above code block is stated below:

  • First, the class named “Node” and its constructor along with the “setNode()” function have been created just like done in the above example.
  • Next, the custom function named “heightCalculation” is calculated, and it accepts two parameters namely “rootNode” and “x”.
  • Inside the function, the provided “rootNode” is checked for null, and if it is null then the value of “-1” is returned.
  • Next, to find the maximum height the left and right subtrees are passed to the “heightCalculation()” function to perform the operation recursively.
  • The default height of the inner nodes is also modified with the left or right subtree values having maximum values.
  • The required node “x” is also matched with each “rootNode” and whenever it gets matched, the height calculated for that rootNode gets stored in the “height” variable. Moreover, the calculated height residing in the “result” variable is returned by the function.
  • To enhance the modularity concept, the “calcHeight()” function is invoked accepting the same “rootNode” and “x” parameters.
  • Inside it, the “heightCalculation()” function is invoked and the “height” variable containing the height for a required node is returned.
  • Finally, create a binary tree by selecting the “left” and “right” nodes and passing their values through the constructor.
  • The value of the node for which the height needs to be found is stored in the “k” variable. The “calcHeight()” function is invoked and the tree name “rootNode” along with the “k” variable is passed to it.

The output of the above code block returns the height for the provided node, as shown below:

How to Calculate the Depth of a Node in a Binary Tree Using JavaScript?

The “depth” of a node tells the depth or number of levels presented in the binary tree. It is calculated by analyzing the number of edges residing between the root node and the selected or targeted node. In the case of finding depth for the whole binary tree, the targeted node is the most distant leaf node. Let’s visit the below steps to understand the procedure of calculating the depth of a node in a Binary tree.

Essential Points/ Working Process

  • If the provided tree is empty or the specified node is not present in the tree, then the value of “-1” is returned.
  • If the provided scenario is false, initialize a random “distance” variable to “-1”.
  • Recursively find the current node starting from the root node to each “left” and “right” subtree.
  • When found add “1” to the “distance” variable showing the height or depth and in case of not found return the stored “distance” value.

Let’s take a look at the visual representation of the calculation of Depth for a tree:

Let’s proceed to the practical demonstration of a JavaScript program to calculate the height of a node in the binary tree:

class Node
{
 constructor()
 {
  this.data = 0;
  this.left = null;
  this.right = null;
 }
};
var setNode = (item) =>
 {
  var tempNode = new Node();
  tempNode.data = item;
  tempNode.left = tempNode.right = null;
  return tempNode;
 }

var calcDepth = (rootNode, y) =>
 {
  if (rootNode == null)
   return -1;

 var distance = -1;
  if ((rootNode.data == y)||(distance = calcDepth(rootNode.left, y)) >= 0 ||
   (distance = calcDepth(rootNode.right, y)) >= 0)
   return distance + 1;
       
  return distance;
 }

var rootNode = setNode(3);
rootNode.left = setNode(6);
rootNode.right = setNode(9);
rootNode.left.left = setNode(12);
rootNode.left.right = setNode(15);
rootNode.left.right.right = setNode(24);
rootNode.right.left = setNode(18);
rootNode.right.right = setNode(21);
var k = 18;

document.write("Depth of a Provided Binary Tree: " + calcDepth(rootNode, k));

The description of the above code is stated below:

  • First, the class named “Node” is created and its default constructor is invoked which initializes the “data” property to “0” and the “left” and “right” properties to “null”.
  • Next, the “setNode()” arrow function is defined, and it accepts a single parameter of “item”. Inside it, the new instance of the “Node” class is created and the parametric “item” value is assigned to the class “data” property.
  • Along with it, the “left” and “right” properties of the class are set to “null” and “tempNode” which is a new instance of the class returned by the function.
  • Then, the “calcDepth()” function is invoked accepting two parameters namely “rootNode” and “x”.
  • This function checks if the provided “rootNode” is equal to “null”. The value of “-1” is returned and identifies if the to-be search node is present in the left or right subtree.
  • If the node is not found in all adjacent nodes, then the value of “1” is added to the “distance” variable, to traverse through the next depth level. If any condition gets executed then, the value of the current “distance” variable will be returned.
  • Finally, create a binary tree by selecting the “left” and “right” nodes and passing their values through the constructor.
  • The value of the node for which the depth needs to be found is stored in the “k” variable. The “calcDepth()” function is invoked and the tree name “rootNode” along with the “k” variable is passed to it.

The output for the above JavaScript code shows that the depth for the node having the value of “18” is “2”:

Alternative Approach to Calculate Height and Depth of a Node in a Binary Tree

The “Level Order Traversal” approach is also used to perform several operations over the binary tree like the calculation of height and depth. The below code block utilizes the “queue” and traverses over each level to find the selected node the depth of that node is received. From this depth, the height of the selected node is then calculated and returned over the console. The practical demonstration is shown below:

class Node {
 constructor(val) {
  this.content = val;
  this.left = null;
  this.right = null;
 }
}

finder = (rootNode, k) =>{
 if (rootNode === null)
  return;

 let nodeDepth = -1;
 let nodeHeight = -1;

 const tempQueue = [];
 tempQueue.push(rootNode);
 let level = 0;

 while (tempQueue.length > 0) {
  const n = tempQueue.length;
   for (let j = 0; j < n; j++) {
    const parentNode = tempQueue.shift();
     if (parentNode.content === k)
      depth = level;
     if (parentNode.left !== null)
      tempQueue.push(parentNode.left);
     if (parentNode.right !== null)
      tempQueue.push(parentNode.right);
    }
   level++;
  }

 nodeHeight = level - nodeDepth - 1;
  console.log("Depth of a Provided Binary Tree: " + nodeDepth);
  console.log("Height of a Provided Binary Tree: " + nodeHeight);
 }


 var rootNode = new Node(3);
 rootNode.left = new Node(6);
 rootNode.right = new Node(9);
 rootNode.left.left = new Node(12);
 rootNode.left.right = new Node(15);
 rootNode.left.right.right = new Node(24);
 rootNode.right.left = new Node(18);
 rootNode.right.right = new Node(21);
 var k = 6;
 
 finder(rootNode, k);

The above code works like this:

  • First, create a class “Node” and its constructor accepts a single parameter of “val” which is assigned to the class “content” property. Its other properties named “left” and “right” are set to “null” by default.
  • Then, a function named “finder()” is created having two parameters of “rootNode” and “k”. Via the “if()” statement the emptiness of “rootNode” is checked and if it is empty, the value of “-1” gets returned.
  • In addition, two variables named “nodeDepth” and “nodeHeight” are created having the default value set to “-1”.
  • The empty queue named “tempQueue” is created and the “rootNode” is passed to it via the “push()” method. Also, Initialize a variable “level” with a “0” value.
  • After that, the “while” loop is utilized which runs till the length of “tempQueue” is greater than “0”. The length of “tempQueue” is stored in the “n” variable. The “for” loop is also used that runs till the length of “tempQueue”.
  • Inside the “for” loop, each element of the “tempQueue” is passed to the “parentNode” variable via the “shift()” method.
  • If this element value gets matched with the provided node then, store the level as a value for the “depth” variable.
  • In case of unmatched, the left and right sides will be added to the “tempQueue” via the “push()” method after checking their nullability.
  • Now, exit the “for” loop and increase the value of the “level” variable by a factor of “1”.
  • After that, retrieve the height of the same node by solving the “level-nodeDepth-1” equation.
  • Finally, create a binary tree by selecting the “left” and “right” nodes and passing their values through the “Node” class constructor.
  • The value of the node for which the depth needs to be found is stored in the “k” variable.
  • The “finder()” function is invoked and the tree name “rootNode” along with the “k” variable is passed to it.

The output generated after the compilation of the above code shows that the depth and height of a desired node are retrieved:

That’s all about the calculation of the height and depth of a node in a binary tree using JavaScript.

Conclusion

To calculate the “height” of a node, the maximum height of a subtree from the left and the right side is retrieved, and the value of “1” is added to the maximum height. In the case of “depth”, the number of edges residing between the root node and the selected or targeted node is retrieved using a recursive function. The “Level Order Traversal” approach is also helpful by the utilization of “queue” and loops. This guide has explained the procedure to calculate the height and depth of a node in a binary tree via JavaScript.

About the author

Abdul Moeed

I'm a versatile technical author who thrives on adaptive problem-solving. I have a talent for breaking down complex concepts into understandable terms and enjoy sharing my knowledge and experience with readers of all levels. I'm always eager to help others expand their understanding of technology.

View all posts