Program to find the height of the tree

Height of a tree is defined as 1, if there is a root node. Height of the tree is nothing but the number of nodes in the longest path of the tree. Below algorithm finds the height of the tree recursively ie, maximum of leftsubtree, rightsubtree and add 1 for each node.

Example

Algorithm

Time Complexity: O(n),

same as Tree Traversal

1. If the tree is empty, return 0
2. else,
    a. recursively calculate the height of the leftsubtree.
    b. recursively calculate the heoght of the rightsubtree.
    c. At each Node, check which subtree height is more and add one to the greater subtree height.

C++ Program

#include<iostream>
using namespace std;

struct Node  //Defining a Node
{
	char data;
	Node* left;
	Node* right;
};

Node* newNode(char data){  //Creating a Node with left and right pointers pointing to NULL
	Node* node = new Node();
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
} 	
int height(Node* node) //Function which returns the size of the tree
{
	if(node!=NULL) // If it is not a null tree
	{
		int lheight = height(node->left);  //recursively calculate the height of the leftsub tree
    	int rheight = height(node->right); //recursively calculate the height of the rightsub tree
    	if (lheight > rheight)			//check for which subtree the height is more and return subtree height +1
    	{ 
    		return(lheight+1);   
    	}
        else
        { 
    		return(rheight+1);
        }
		
	}
	else			
	{
		return 0; //If there is no node return 0 as the height
	}

}
int main()
{
	Node* root = newNode('A');  //Assigning the Node values
	root->left = newNode('B');
	root->right = newNode('C');
	root->left->left = newNode('D');
	root->left->right = newNode('E');
	root->right->left = newNode('F');		
	cout<<"Height of the tree is "<<height(root); //Printing the height of the tree
	return 0;

}
Try It


< Prev
Scroll to Top