Height of Binary Search Tree - Recursive Approach

In this article, we are going to see how to get the height of a Binary Search Tree using a Recursive Approach. The height of the Binary Tree is defined as the number of edges in the longest path from the root to the leaf node.

Base Case Height of the Binary Search Tree:

• If the root is null, no nodes are present in the Binary Search Tree then the Height is -1
• If only one node is present i.e root then the Height is 0

In this problem we can divide the problem into smaller parts by using:

Height of Tree = 1 + MAX(Height of Left Subtree, Height of Right Subtree)

And then we further apply the same to the left subtree and to the right subtree till we reach the Base Case of the subtree being null and then we return -1.

Below is an example of a Binary Tree:

The height of the Below Binary Tree is 2

So the height of Node 4 = 1 + MAX(Height of Node 2 + Height of Node 7) = 1 + MAX(1,0) = 2

Algorithm

1. If the node is null, it means that the tree is empty and so return -1
2. Get the leftHeight by calling the function and passing the left of the node to it
3. Get the rightHeight by calling the function and passing the right of the node to it
4. Get the max of leftHeight and rightHeight and store it in maxHeight
5. Return maxHeight + 1

Complexity

• Time Complexity: O(N)
• Auxiliary Space Complexity: O(Height of Tree)

The Time Complexity will be O(N) as visit every node once, and the space complexity will be O(Height of Tree) which is O(logN) for a perfect binary tree, the Space Complexity is because of the stack memory consumed by the recursive calls.

Code

# Java Code

class BinarySearchTree {
 class Node {

   // Node class for Binary Search Tree
   int data;
   Node left, right;

   // Constructor to set the value of the node
   Node(int data) {
     this.data = data;
     this.left = null;
     this.right = null;
   }
 }

 private Node root = null;

 // Insert array of num into the BST
 public void insertArray(int nums[]) {
   for (int i = 0; i < nums.length; i++) {
     insert(nums[i]);
   }
 }

 // Insert a value in BST Iteratively
 public void insert(int data) {

   // Check if root is null,
   // if null then create a node and make it root
   if (root == null) {
     root = new Node(data);
     return;
   }

   // Start traversing from the root and find the position of node to insert
   Node current = root;

   while (current != null) {

     if (data < current.data) {

       // Insert the node if the position is empty
       if (current.left == null) {
         current.left = new Node(data);
         return;
       }
       current = current.left;

     } else {

       if (current.right == null) {
         // Insert the node if the position is empty
         current.right = new Node(data);
         return;
       }
       current = current.right;

     }
   }
 }


 public int getHeightRecursive() {
   // call the callback function and provide the root
   return getHeightCallback(root);
 }


 private int getHeightCallback(Node node) {

   // If the node is null then it's height is given as -1
   if (node == null)
     return -1;

   // Get the height of both left and right node
   int leftHeight = getHeightCallback(node.left);
   int rightHeight = getHeightCallback(node.right);

   // Store the max of left and right node height in maxHeight
   int maxHeight = Math.max(leftHeight, rightHeight);

   // since the node will have 1 + maxHeight of children
   // As the node is 1 height above the childrens
   return maxHeight + 1;
 }


 public static void main(String[] args) {

   int[] nums = { 4, 7, 2, 1, 3 };
   BinarySearchTree bst = new BinarySearchTree();
   bst.insertArray(nums);

   // It gives height of the binary tree height of the root node is 0,
   // and if no node is there we take -1
   int height = bst.getHeightRecursive();

   System.out.println("Height of Binary Tree: " + height);

 }
}

Output

Height of Binary Tree: 2