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.



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

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 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