Binary Tree: Find the height - Iterative approach


Write a program to find the height of a binary 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

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

There are various interpretations for height of a binary tree.
Some people consider height in terms of edges (the line connecting the two nodes) while other people consider the no of nodes in the longest path from root to leaf node.
And some people also consider levels to calculate height (root node is at level 1, its child nodes are at level 2 and the final leaf nodes are at level n, so the height becomes n)
So its important to call out how do you interpret the height of a binary tree

Here we are considering levels of the binary tree to calculate the BT height

 
Approach

To find the height of a Binary Tree using Iterative Approach we traverse the given Binary Search Tree Level by Level and keep incrementing the height variable.
We will use Breadth First Search Traversal for level wise traversal on the Binary Tree

 
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 BT in it, this Queue is used for the BFS traversal
  4. While the currentLevelNodes is not empty do
    • Create a nextLevelNodes Queue to store all the nodes in the next level
    • While currentLevelNodes is not empty do
      • Get the First Node from the currentLevelNodes and store it in a variable named current
      • If left of current is not null, then push left of current to nextLevelNodes
      • If right of current is not null, then push right of current to nextLevelNode
    • Copy the nextLevelNodes to the currentLevelNodes
    • Increment the value of Height by 1
  5. Return Height
 
Diagram

 
Complexity

Time Complexity : O(n) , where n is the number of nodes in binary tree
Space Complexity: O(Max Width of the BT)

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

 
Java Code
import java.util.ArrayDeque;
    import java.util.Queue;
    
    class BinaryTreeHeightIterative{
        // Node Class to represent the each node of BinaryTree
        static class Node {
            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;
    
        // A function which prints the level order traversal representation of the Binary Tree
        static void printTree(Node root) {
            // Queue to store the current level of the binary tree
            Queue currentLevelQueue = new ArrayDeque();
            currentLevelQueue.offer(root); // Insert the root to the queue
    
            while (!currentLevelQueue.isEmpty()) {
                
                // Create a temporary queue to store the nodes of next level
                Queue tempQueue = new ArrayDeque();
                
                while (!currentLevelQueue.isEmpty()) {
                    
                    // Get the node from the queue and print it
                    Node current = currentLevelQueue.poll();
                    
                    System.out.print(current.data);
    
                    // If current node has left then insert it to the tempQueue
                    if (current.left != null) {
                        tempQueue.offer(current.left);
                    }
    
                    // If current node has right then insert it to the tempQueue
                    if (current.right != null) {
                        tempQueue.offer(current.right);
                    }
                }
                
                // Printing a new line at each level end
                System.out.println();
    
                // copy the contents of the tempQueue to the currentLevelQueue
                currentLevelQueue = tempQueue;
            }
        }
    
        public int getHeightIterative(Node node) {
            // Create a variable to store the height
            int height = -1;
    
            // If the root is null then the height of the tree is -1
            if (node == null) {
                return -1;
            }
    
            Node temp = node;
    
            // Create a queue to store the nodes in the current level of the bfs traversal
            Queue currentLevelNodes = new ArrayDeque();
    
            // Push the root to the queue to initialize it
            currentLevelNodes.offer(temp);
    
            // Run the loop till we have node in the current level
            while (!currentLevelNodes.isEmpty()) {
                // Create a queue to track the next level nodes
                Queue nextLevelNodes = new ArrayDeque();
    
                // 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) {
            // Creating a simple binary tree using the node class
            Node tree1 = new Node(1);
            tree1.left = new Node(2);
            tree1.right = new Node(3);
            tree1.left.left = new Node(4);
            tree1.left.right = new Node(5);
            tree1.right.left = new Node(6);
            tree1.right.right = new Node(7);
    
            BinaryTreeHeightIterative btHeight = new BinaryTreeHeightIterative();
    
            printTree(tree1);
            int height = btHeight.getHeightIterative(tree1);
            System.out.println("Height of Binary Tree: " + height);
        }
  }
 
Output

1
23
4567
Height of Binary Tree: 2



Thanks for feedback.



Read More....
Check if a binary tree is a min heap
Check if a binary tree is symmetric or mirror of itself
Check if a binary tree is symmetric or mirror of itself - iterative
Create a mirror of binary tree - Iterative approach
Create a mirror of binary tree - Recursive approach