Recursive JavaScript Problem: Finding the Height of a Binary Tree

Explore how recursion in JavaScript efficiently calculates the height of a binary tree, providing a step-by-step guide and code examples.

The ‘Node’ Class

class Node {

  constructor(data) {

    this.data = data;

    this.left = null;

    this.right = null;

  }

}

The Node class represents a node in a binary tree. Each node has three properties:

• data: Stores the value of the node.

• left: Points to the left child node (initially null).

• right: Points to the right child node (initially null).

BinaryTree Class

class BinaryTree {
  constructor() {
    this.root = null;
  }

The BinaryTree class represents the binary tree itself. It has a single property:

• root: Points to the root node of the tree (initially null).

insertIterative - Method in the BinaryTree Class

This insertIterative method is used for the insertion of nodes inside of the binary tree.

  insertIterative(data) {
    const newNode = new Node(data);
    // root is null
    if (this.root === null) {
      this.root = newNode;
    } else {
      let currentParentNode = this.root;
      while (true) {
        if (data < currentParentNode.data) {
          // insert on left
          if (currentParentNode.left === null) {
            currentParentNode.left = newNode;
            break;
          }
          currentParentNode = currentParentNode.left;
        } else {
          // insert on right
          if (currentParentNode.right === null) {
            currentParentNode.right = newNode;
            break;
          }
          currentParentNode = currentParentNode.right;
        }
      }
    }
  }

The insertIterative method adds a new node to the tree with the given data. Here's how it works:

1. Create a new node: A new Node instance is created with the given data.

2. Check if the tree is empty: If the root is null, the new node becomes the root.

3. Iterate to find the correct position: Starting from the root, the method compares the data with the current node's data:

   • If data is less than the current node's data, move to the left child.

   • If data is greater than or equal to the current node's data, move to the right child.

4. Insert the node: When a null left or right child is found, insert the new node there.

height Method - Method in the BinaryTree Class

The height method calculates the height of the tree (or subtree) rooted at the given root node. The height of a tree is the number of edges on the longest path from the root to a leaf.

  height(root) {
    if (root === null) {
      return 0;
    }
    let leftHeight = this.height(root.left);
    let rightHeight = this.height(root.right);

    return Math.max(leftHeight, rightHeight) + 1;
  }
}

Here's how it works:

1. Base case: If the root is null, return 0 (an empty tree has height 0).

2. Recursive case: Calculate the height of the left and right subtrees recursively.

3. Return the maximum height: The height of the tree is the greater of the left and right subtree heights, plus 1 for the current node.

Using the BinaryTree Class - Driver code

const tree = new BinaryTree();
tree.insertIterative(5);
tree.insertIterative(3);
tree.insertIterative(4);
tree.insertIterative(2);
tree.insertIterative(9);
tree.insertIterative(1);

console.log("Height of binary tree:", tree.height(tree.root));

Here's how the BinaryTree class is used:

1. Create a new tree: A new BinaryTree instance is created.

2. Insert nodes: Nodes with values 5, 3, 4, 2, 9, and 1 are inserted iteratively into the tree.

3. Calculate the height: The height of the tree is calculated using the height method and printed.

In conclusion, exploring how recursion calculates the height of binary trees in JavaScript shows the beauty and usefulness of recursive thinking in handling tree structures.