JSInterview30:Part 3-Finding the Height of Binary Tree

Title image

Introduction:

Binary trees are hierarchical data structures consisting of nodes, where each node has at most two children: left and right. They are widely used in computer science and are fundamental in representing hierarchical relationships. One common task when working with binary trees is finding the height of the tree, which is the longest path from the root node to a leaf node. In this article, we’ll explore how to write a JavaScript function to find the height of a binary tree.

Steps:

1. Define the Binary Tree Node: Before we can find the height of a binary tree, we need to define a node structure that represents each node in the tree. Each node will have a value and references to its left and right children.
2. Write the Height Calculation Function: We’ll implement a recursive function to calculate the height of the binary tree. The function will traverse the tree recursively, keeping track of the height as it moves down the tree.
3. Handle Base Cases: In our recursive function, we’ll handle base cases where we reach a leaf node or a null node (representing an empty subtree).
4. Calculate the Height: Using recursion, we’ll calculate the height of the left and right subtrees and return the maximum height plus one.
5. Test the Function: Finally, we’ll test our function with different binary trees to ensure it works correctly.

Implementation:

Code explanation

Let’s break down the provided JavaScript code step by step using the same example mentioned in the code snippet:

Step 1: Define the Binary Tree Node

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Here, we define a class TreeNode to represent each node in the binary tree. Each node has a value property to store the value of the node, and left and right properties to reference its left and right children, respectively.

Step 2: Write the Height Calculation Function

function findHeight(root) {
  if (root === null) {
    return 0;
  }
  
  let leftHeight = findHeight(root.left);
  let rightHeight = findHeight(root.right);
  
  return Math.max(leftHeight, rightHeight) + 1;
}

The findHeight function takes the root of the binary tree as its parameter. It recursively calculates the height of the binary tree. If the root is null (representing an empty subtree), it returns 0. Otherwise, it calculates the height of the left and right subtrees recursively and returns the maximum height plus one.

Step 3: Test the Function

We create a binary tree with the following structure:

      1
     / \
    2   3
   / \
  4   5

Then, we call the findHeight function with the root node of the binary tree (root). The output will be the height of the binary tree, which is 3.

Live demo:- Codepen

This log output of calcualted heights will help you in understanding the working better:-

// Height for node 4
"root value" 4
"left Height" 0 "right height" 0
"Maxheight" 1

// Height for node 5
"root value" 5
"left Height" 0 "right height" 0
"Maxheight" 1

"root value" 2
"left Height" 1 "right height" 1
"Maxheight" 2

"root value" 3
"left Height" 0 "right height" 0
"Maxheight" 1


"root value" 1
"left Height" 2 "right height" 1
"Maxheight" 3

Conclusion:

In this article, we explored the concept of binary trees and how to find the height of a binary tree using JavaScript. We defined the structure of a binary tree node, implemented a recursive function to calculate the height, and tested our function with a sample binary tree. Understanding how to find the height of a binary tree is essential for various applications, such as optimizing tree-based algorithms and data storage. Hope this helps in your future interview rounds. Have a nice day ahead 😁