Height of Binary Tree

Given with the binary tree, find the height of the tree.

Height of the binary tree is one more than the largest number of edges in the path from the root node to the lowest level leaf node.

Problem Statement

We are given a binary tree as input and we need to find the height of binary tree. In other words, we are given a binary tree and we need to calculate the maximum depth of the binary tree.

Note : The height of an empty binary tree is -1, and the height of a binary tree having only one node is 0.

Refer to the Example and Example Explanation sections for more details and the Approach section to understand how to find the height of binary tree.

Example

Example : 1

The given binary tree (input) is : $[ 5, 3, 6, 2, 4 ]$.

Tree formed is :

      5
     / \
    3   6
   / \
  2   4

Output :

The height of binary tree is: 3.

Example : 2

The given binary tree (input) is : $[ 15, 10, 20, 8, 12, 16, 25, 9 ]$.

Tree formed is :

       15
     /    \
    10     20
   / \     / \
  8  12   16  25
  \
   9

Output :

The height of binary tree is: 4.

Example Explanation

Before getting into the explanation of the example and how to find height of binary tree, let us first get a brief introduction about the binary tree and the height of a binary tree.

A binary tree can be defined as a collection of objects or elements or entities known as nodes. These nodes are linked together to represent a hierarchy.

The top node of the hierarchy is known as the root node. Each node of a binary tree contains some data and it can have at most two child nodes. A root node can never have a parent node. The nodes that do not have any child nodes are termed leaf nodes.

Example :

Now, the height of the binary tree is one more than the largest number of edges in the path from the root node to the lowest level leaf node.

In other words, we can say that the height of binary tree is the height of the root node in the entire binary tree.

In the example :

      5
     / \
    3   6
   / \
  2   4

The root node is $5$ and the lowest level leaf nodes are $2$ and $4$. Now, in the above example, we have the first edge from $5$ to $3$, and the second edge from $3$ to $2$. So, the height of the binary tree comes out to be $3$ [a number of edges + 1].

Constraints

• $1 <=$ Number of nodes $<= 10^5$
• $1 <=$ Data of a node $<= 10^5$

In some problems, you may find the number of test cases represented by t. So, we only need to call the findHeight() function t-times.

Approach : 1

We can easily calculate the height of binary tree using recursion. The idea is very simple, we will calculate the height of the current level, and recursively call the findHeight() function for the left sub-tree and right sub-tree (if they exist).

Now, the height of the current level will be the maximum of the height of the left sub-tree and the height of the right sub-tree.

So, the recursive function will provide the height of the left sub-tree and right sub-tree and we will assign the height of the current node as the maximum of them.

We are recursively left sub-tree and right sub-tree because a node can have a left or a right child or both. Refer to the pseudo-code for a better understanding of the recursive algorithm to find the height of the binary tree.

Algorithm :

The pseudo-code for the same :

1. Check base case :

• If the tree is empty, return -1 as we cannot find its height.
• Else, continue the further steps.

1. Call the findHeight(root) function for the left subtree and store the result.
2. Call the findHeight(root) function for the right subtree and store the result.
3. Get the maximum of both the heights and assign the height as the result :

• height = max(left_height, right_height)

1. Return the result as (height + 1), as we need to add the current node in the total height as well.

Code Implementation

Let us the code implementation of the same in various languages :

C++ Code :

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

/*
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.
*/
class Node {
public:
   int data;
   Node *left;
   Node *right;
};

/*
A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
*/
int findHeight(Node *node) {
   // Base case: If the tree is empty, return -1 as we cannot find its height.
   if (node == NULL)
      return 0;
   else {
      /* Call the findHeight() function for the left and right sub tree and store the results.
       */
      int leftHeight = findHeight(node->left);
      int rightHeight = findHeight(node->right);

      // returning the (maximum + 1) as the height of the binary tree.
      if (leftHeight > rightHeight)
         return (leftHeight + 1);
      else
         return (rightHeight + 1);
   }
}

/* A function that will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
 */
Node *addNode(int data) {
   Node *newNode = new Node();
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;

   return newNode;
}

// main function
int main() {
   // creating object of the Node class.
   Node *root = addNode(1);

   root->left = addNode(2);
   root->right = addNode(3);
   root->left->left = addNode(4);
   root->left->right = addNode(5);

   cout << "The height of binary tree is: " << findHeight(root);
   return 0;
}

Java Code :

/*
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.
*/
class Node {
    int data;
    Node left, right;
    /* The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
    */
    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    // creating reference of the Node class.
    Node root;

    /*
    A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
    */
    int findHeight(Node node) {

        // Base case: If the tree is empty, return -1 as we cannot find its height.

        if (node == null)
            return 0;

        else {
            /* Call the findHeight() function for the left and right sub tree and store the results.
            */
            int leftHeight = findHeight(node.left);
            int rightHeight = findHeight(node.right);

            // returning the (maximum + 1) as the height of the binary tree.
            if (leftHeight > rightHeight)
                return (leftHeight + 1);
            else
                return (rightHeight + 1);
        }
    }

    public static void main(String[] args) {

        // creating object of the BinaryTree class.
        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("The height of binary tree is: " +
                tree.findHeight(tree.root));
    }
}

Python Code :

"""
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.

The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to None as there is no child currently.
"""
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


"""
A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
"""
def findHeight(node):
    if node is None:
        return 0

    else:

        # Call the findHeight() function for the left and right sub tree and store the results.
        leftHeight = findHeight(node.left)
        rightHeight = findHeight(node.right)

        # returning the (maximum + 1) as the height of the binary tree
        if (leftHeight > rightHeight):
            return leftHeight+1
        else:
            return rightHeight+1


if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    print("The height of binary tree is: ", findHeight(root))

Output :

The height of binary tree is: 3.

Time Complexity :

In the recursive approach of finding the height of binary tree, we are traversing all the nodes of the binary tree. So, the time complexity of the algorithm comes out to be $O(n)$, where n is the number of nodes in the binary tree.

Space Complexity :

In the above code, we are not using any extra space but there is recursive calls of the findHeight() function. So, the space complexity comes out to be $O(n)$ as well.

Approach : 2

Another approach to finding the height of the binary tree is to perform the Bread First Search (BFS) or the level order traversal of the binary tree.

We will keep on incrementing the height when we advance to the next level. For performing the level order traversal, we need to use the queue data structure.

The idea is quite simple, we would take a queue and insert the root node into it and initialize a height variable.

Now, we would remove a node from the queue (dequeue) and explore its left and right child, after the exploration, we will increment the height counter by one as each exploration denotes that the current level is done and we should move to the next level.

Note : The level order traversal way of finding the height of the binary tree is also known as the iterative way.

Refer to the pseudo-code provided below for a better understanding.

Algorithm :

The pseudo-code for the same :

1. Initialize a queue and a height variable.
2. Insert the root node into the queue.
3. Remove all the nodes that are currently present in the queue.
4. Add all the children nodes i.e. left or right child (if present) and increment the height counter by 1.
5. After all the nodes are explored (i.e. the queue becomes empty), return height as result.

Code Implementation

Let us the code implementation of the same in various languages :

C++ Code :

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

/*
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as left and right pointer which points to its left and right child.
*/
class Node {
public:
   int data;
   Node *left;
   Node *right;
};

/*
A function that finds the height of the binary tree by maximum height between the left and right subtree.
*/
int findHeight(Node *root) {
   // Initialize a queue and a height variable.
   int height = 0;

   queue<Node *> q;

   // Insert the root node into the queue and a null to mark last
   q.push(root);
   q.push(NULL);

   // running the discussed steps until the queue becomes empty
   while (!q.empty()) {
      // removing the node from the queue.
      Node *temp = q.front();
      q.pop();

      // if NULL is encountered, increment the height counter.
      if (temp == NULL)
         height++;

      // if NULL is not encountered, explore left and right child
      if (temp != NULL) {
         if (temp->left)
            q.push(temp->left);

         if (temp->right)
            q.push(temp->right);
      }
      else if (!q.empty())
         q.push(NULL);
   }
   return height;
}

/* A function that will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
 */
Node *addNode(int data) {
   Node *newNode = new Node();
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;

   return newNode;
}

// main function
int main() {
   // creating object of the Node class.
   Node *root = addNode(1);

   root->left = addNode(2);
   root->right = addNode(3);
   root->left->left = addNode(4);
   root->left->right = addNode(5);

   cout << "The height of binary tree is: " << findHeight(root);
   return 0;
}

Java Code :

import java.util.*;
/*
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as left and right pointer which points to its left and right child.
*/
class Node {
    int data;
    Node left, right;
    /* The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
    */
    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    // creating reference of the Node class.
    Node root;

    /*
    A function that finds the height of the binary tree by maximum height between the left and right subtree.
    */
    int findHeight(Node root) {
        // Initialize a queue and a height variable.
        int height = 0;

        Queue<Node> q=new LinkedList<>();

        // Insert the root node into the queue and a null to mark last
        q.add(root);
        q.add(null);

        // running the discussed steps until the queue becomes empty
        while (!q.isEmpty()) {
        // removing the node from the queue.
        Node temp = q.peek();
        q.remove();

        // if NULL is encountered, increment the height counter.
        if (temp == null)
            height++;

        // if NULL is not encountered, explore left and right child
        if (temp != null) {
            if (temp.left != null)
                q.add(temp.left);

            if (temp.right != null)
                q.add(temp.right);
        }
        else if (!q.isEmpty())
            q.add(null);
        }
        return height;
    }

    public static void main(String[] args) {

        // creating object of the BinaryTree class.
        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("The height of binary tree is: " +
                tree.findHeight(tree.root));
    }
}

Python Code :

"""
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as left and right pointer which points to its left and right child.

The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to None as there is no child currently.
"""


class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


"""
A function that finds the height of the binary tree by maximum height between the left and right subtree.
"""


def findHeight(node):
    # Initialize a queue and a height variable.
    height = 0
    q = []

    # Insert the root node into the queue and None to mark last
    q.append(root)
    q.append(None)

    # running the discussed steps until the queue becomes empty
    while(len(q) > 0):
        # removing the node from the queue.
        temp = q[0]
        q = q[1:]

        # if None is encountered, increment the height counter.
        if(temp == None):
            height += 1

        # if None is not encountered, explore left and right child
        if(temp != None):
            if(temp.left):
                q.append(temp.left)

            if(temp.right):
                q.append(temp.right)

        elif(len(q) > 0):
            q.append(None)
    return height


if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)

    print("The height of binary tree is: ", findHeight(root))

Output :

The height of binary tree is: 3.

Time Complexity :

In the iterative approach of finding the height of binary tree, we are traversing all the nodes of the binary tree. So, the time complexity of the algorithm comes out to be $O(n)$, where n is the number of nodes in the binary tree.

Space Complexity :

In the above code, we are using extra space as a queue. So, the space complexity comes out to be $O(n)$ as well where n is the size of the queue or the number of nodes (inserted into the queue data structure).

Conclusion

• A binary tree can be defined as a collection of objects or elements or entities known as nodes. These nodes are linked together to represent a hierarchy.
• The height of the binary tree is one more than the largest number of edges in the path from the root node to the lowest level leaf node.
• The recursive approach to finding the height of binary tree can be calculating the height of the current level, and recursively calling the findHeight() function for the left sub-tree and right sub-tree (if they exist).
• In the recursive approach of finding the height of binary tree, the time complexity of the algorithm comes out to be $O(n)$, where n is the number of nodes in the binary tree.

In the recursive approach, we are not using any extra space but there is recursive calls of the findHeight() function. So, the space complexity comes out to be $O(n)$ as well.

• Another approach to finding the height of the binary tree is to perform the Bread First Search (BFS) or the level order traversal of the binary tree. We will keep on incrementing the height when we advance to the next level.
• In the iterative approach of finding the height of binary tree, the time complexity of the algorithm comes out to be $O(n)$, where n is the number of nodes in the binary tree.
• In the recursive approach, we are using extra space as a queue. So, the space complexity comes out to be $O(n)$ as well where n is the size of the queue or the number of nodes (inserted into the queue data structure).