Iterative Method to find Height of Binary Tree  

Difficulty Level Medium
Frequently asked in Accolite Adobe Amazon Fanatics Fourkites Hike Snapdeal Yatra
Binary Tree Queue Tree

Problem Statement  

The problem “Iterative Method to find Height of Binary Tree” states that you are given a binary tree, find the height of the tree using the iterative method.

Examples  

Input
Iterative Method to find Height of Binary TreePin

3

Input
Iterative Method to find Height of Binary TreePin

4

Algorithm for Iterative Method to find Height of Binary Tree  

The height of a tree also equals the number of levels in the tree. So to find the height using iteration, do a level order traversal of the tree and count the number of levels in it.

Please click Like if you loved this article?

  1. Create a queue and push the root to it. Initialize height as 0.
  2. While the queue is not empty repeat steps 3 and 4.
  3. At this moment the queue contains one level of the tree. Increment height by 1. Initialize a variable size as the size of the queue.
  4. Run a loop from 1 to size, and at each iteration remove an element from the queue and push its children to the queue. This step will remove one level from the queue and push the next level to it.
  5. Return height.
See also
Sequences of given length where every element is more than or equal to twice of previous

Explanation

Consider the tree shown in first example,

Step 1:

Push root to queue and initialize height as 0, that is,
queue = 2, height = 0

Step 2:

Repeat step 3 and 4 while queue is not empty.

Step 3 and 4:

Please click Like if you loved this article?

Iteration 1:
The queue contains the first level of tree.
Increment height, so height = 1.
Remove all the elements of queue and add their children to the queue.
queue = 7 -> 11

Iteration 2:
Queue contains the second level of the tree.
Increment height, so height = 2.
Remove all the elements of queue and add their children to the queue.
queue = 5 -> 9 -> 3

Iteration 3:
Queue contains the third level of the tree.
Increment height, so height = 3.
Remove all the elements of queue and add their children to the queue.
queue = null

As the queue becomes empty, so we stop here.

Step 5:

Return height, so the height of the tree is 3.

Code  

Java code for Iterative Method to find Height of Binary Tree

import java.util.LinkedList;
import java.util.Queue;

class IterativeMethodToFindHeightOfBinaryTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int height(Node root) {
        if (root == null) {
            return 0;
        }

        // create a queue and push root to it
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        // initialise height as 0
        int height = 0;

        // do a level order traversal
        // while queue is not empty
        while (!q.isEmpty()) {
            // increment height
            height++;
            // initialise size as size of queue
            int size = q.size();
            // Remove current level from queue and push next level
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = q.poll();
                // push current element's children to the queue
                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);
            }
        }
        
        // return height
        return height;
    }

    public static void main(String[] args) {
        // Example Tree 1
        Node root1 = new Node(2);
        root1.left = new Node(7);
        root1.right = new Node(11);
        root1.left.left = new Node(5);
        root1.right.left = new Node(9);
        root1.right.right = new Node(3);

        System.out.println(height(root1));

        // Example Tree 2
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);
        root2.right.right = new Node(6);
        root2.left.left.left = new Node(7);
        root2.left.left.right = new Node(8);
        root2.right.right.left = new Node(9);
        root2.right.right.right = new Node(10);

        System.out.println(height(root2));
    }
}
3
4

C++ Code for Iterative Method to find Height of Binary Tree

#include <bits/stdc++.h>
using namespace std;

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;     
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with data d
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

int height(Node *root) {
    if (root == NULL) {
        return 0;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialise height as 0
    int height = 0;
    
    // do a level order traversal
    // while queue is not empty
    while (!q.empty()) {
        // increment height
        height++;
        // initialise size as size of queue
        int size = q.size();
        // Remove current level from queue and push next level
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            // push current element's children to the queue
            q.pop();
            if (curr->left != NULL)
                q.push(curr->left);
            if (curr->right != NULL)
                q.push(curr->right);
        }
    }
    
    // return height
    return height;
}

int main() {
    // Example Tree 1
    Node *root1 = newNode(2);
    root1->left = newNode(7);
    root1->right = newNode(11);
    root1->left->left = newNode(5);
    root1->right->left = newNode(9);
    root1->right->right = newNode(3);

    cout<<height(root1)<<endl;

    // Example Tree 2
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
    root2->right->right = newNode(6);
    root2->left->left->left = newNode(7);
    root2->left->left->right = newNode(8);
    root2->right->right->left = newNode(9);
    root2->right->right->right = newNode(10);

    cout<<height(root2)<<endl;
    
    return 0;
}
3
4

Complexity Analysis  

Time Complexity

O(n), where n is the number of nodes in the binary tree. Since we have used a queue and traversed over all the nodes in the binary tree. So it’s clear that the time complexity is linear.

Please click Like if you loved this article?

See also
Rearrange an Array Such that arr[i] is equal to i

Space Complexity

O(n), where n is the number of nodes in the binary tree. As already told that we have used a queue to find the height, we had stored the elements in that queue. Thus the space complexity is also linear.

References

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh