Height of Binary Search Tree - Iterative Approach

 In this article, we will see how to get the height of a Binary Search Tree using iterative 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

To find the height of a Binary Search Tree using iterative approach we traverse the given Binary Search Tree level by level and keep incrementing the height variable. So to travel level by level we use Breadth First Search Traversal on the Binary Search Tree.

Below is an example of a Binary Search Tree:

Traversal of the Binary Search Tree level by level will be

Height 0: 4
Height 1: 2 7
Height 2: 1 3

The height of the Below Binary Tree is 2

Algorithm

1. Create a variable height having value -1
2. If the root of the tree is null, then return -1
3. Create a currentLevelNodes Queue and insert root of BST in it, this Queue is used for the BFS traversal
4. While the currentLevelNodes is not empty do:
   1. Create a nextLevelNodes Queue to store all the nodes in the next level
   2. While currentLevelNodes is not empty do:
      1. Get the First Node from the currentLevelNodes and store it in a variable named current
      2. If left of current is not null, then push left of current to nextLevelNodes
      3. If right of current is not null, then push right of current to nextLevelNode
   3. Copy the nextLevelNodes to the currentLevelNodes
   4. Increment the value of Height by 1
5. Return Height

Complexity

• Time Complexity: O(N)
• Space Complexity: O(Max Width of the BST)

The Time Complexity will be O(N) as visit every node once, and the space complexity will be O(Max Width of the BST), the Space Complexity is because of the Queue used to store the nodes in the current and next level of the Binary Search Tree.

Code

# Java Code

import java.util.ArrayDeque;
import java.util.Queue;


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 getHeightIterative() {
   // Create a variable to store the height
   int height = -1;


   // If the root is null then the height of the tree is -1
   if (root == null) {
     return -1;
   }


   // Create a queue to store the nodes in the current level of the bfs traversal
   Queue<Node> currentLevelNodes = new ArrayDeque<Node>();


   // Push the root to the queue to initialize it
   currentLevelNodes.offer(root);


   // Run the loop till we have node in the current level
   while (!currentLevelNodes.isEmpty()) {
     // Create a queue to track the next level nodes
     Queue<Node> nextLevelNodes = new ArrayDeque<Node>();


     // Loop through all the nodes in the current level
     while (!currentLevelNodes.isEmpty()) {
       // Get the current node from the queue
       Node current = currentLevelNodes.poll();


       // Check if the current has children and push the children in nextLevelQueue
       if (current.left != null) {
         nextLevelNodes.offer(current.left);
       }


       if (current.right != null) {
         nextLevelNodes.offer(current.right);
       }
     }


     // Copy the next level nodes into the current level queue
     currentLevelNodes = nextLevelNodes;


     // Increment the height as we go to the nextLevel
     height++;
   }


   return height;
 }


 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.getHeightIterative();
   System.out.println("Height of Binary Tree: " + height);
 }
}

Output

Height of Binary Tree: 2