Height Of A Binary Tree in C++

January 21, 2021

Height Of The Tree

The height of a binary is tree is defined as the number of edges between the root node and the farthest leaf node.The height of an empty tree is 0 and height of the tree given in the image is 3.

calculating height of a binary tree in C++

Common Uses Of Finding Height Of Tree

  1. To check whether the tree is an AVL tree or not. An AVL tree is a binary search tree in where the difference of left and right subtree is less than or equal to one for all nodes.
  2. To Print Level Order Traversal using recursion.
  3. The number of nodes in a perfect binary tree can be determined using height of the tree.

Algorithm:

  1. If root is NULL, return 0.
  2. Otherwise Recursively call the height function on its left and right child.
  3. Return the value which is greater out of height of left child and bight of right child

Code:

#include<bits/stdc++.h> 
using namespace std; 
class Tree {
    public:
        int data;
        Tree* left = NULL,*right = NULL;
        // Constructor initialised
        Tree(int x) {
            data = x;
            left = NULL;
            right = NULL;
        }
};
int height(Tree *root) {
    if (root == NULL) return 0; // Checking whether node null or not
    // Else return the max of the height of left subtree or right subtree
    return (1 + max(height(root->left),height(root -> right)));
}
int main() {
    Tree *root = new Tree(10);
    root -> left = new Tree(20);
    root -> right = new Tree(30);
    root -> left -> left = new Tree(40);
    root -> left -> right = new Tree(50);
    cout << height(root);
    return 0;
}

Output:

3

Time Complexity
For Height Of a Tree

Time Complexity

O(n)

Space Complexity

O(n)