Height Of The Binary Tree

Last updated: 29th Aug, 2020

Problem Statment

Given a binary tree, find its height.

Example 1:

          1
        /    \
     2       3

>> 2

Example 2:

          2
            \
            1
            /
          3

>> 3

Approach

In this problem, we need to find out the maximum height of the binary tree. The height of the binary tree can be defined as the number of nodes between root and a leaf. Maximum height will be the number of levels between root and deepest leaf. To solve this problem, we traverse through the left subtree and calculate the height of the left subtree. Again, calculate the height of the right subtree by traversing through it. Maximum height will be maximum of the height of the left subtree and right subtree.

Time and Space Complexity :
Time Complexity: O(N)
Space Complexity : O(1)

C++ Code


#include <iostream>
using namespace std;

class Node
{
  int key;
  Node *left, *right;

  Node(int key)
  {
	  this->key = key;
	  this->left = this->right = nullptr;
  }
};

int height(Node* root)
{
  if (root == nullptr)
  	return 0;
  return 1 + max(height(root->left), height(root->right));
}

int main()
{
    Node* root = nullptr;

    root = new Node(15);
    root->left = new Node(10);
    root->right = new Node(20);
    root->left->left = new Node(8);
    root->left->right = new Node(12);
    root->right->left = new Node(16);
    root->right->right = new Node(25);

    cout << "The height of the binary tree is " << height(root);

    return 0;
}

Python Code

 # Data structure to store a Binary Tree node
class Node:
  def __init__(self, key=None, left=None, right=None):
    self.key = key
    self.left = left
    self.right = right


  # Recursive function to calculate height of given binary tree
  def height(root):

    # Base case: empty tree has height 0
    if root is None:
      return 0

    # recur for left and right subtree and consider maximum depth
    return 1 + max(height(root.left), height(root.right))


if __name__ == '__main__':

root = Node(15)
root.left = Node(10)
root.right = Node(20)
root.left.left = Node(8)
root.left.right = Node(12)
root.right.left = Node(16)
root.right.right = Node(25)

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