Find the height of the given binary tree.
Every tree has a height, which is defined as the maximum number of nodes that must be visited on any path from the root to a leaf.
Its simple , isn’t it? If you don’t already know what are trees and binary tress, You would like to go through What are Trees and What is a Binary Tree.
1- traverse all left nodes recursively say, h1
2-traverse all right nodes recursively say,h2
height is max(h1,h2)
It can be coded as:
int height(struct tnode *p)
{
struct tnode *temp=p;
int h1=0,h2=0;
if(p==NULL)return(0);
if(p->left){h1=height(p->left);}
if(p->right){h2=height(p->right);}
return(max(h1,h2)+1);
}
The number of the nodes in the binary tree can be found as:
int number(struct tnode *p)
{
if(p == NULL)
return 0;
else
return (number(p->left)+number(p->right)+1);
}
Also check the Traversal of Binary Search Tree to see why the height of a binary tree is very important.
#1 by Sagar Rohankar on March 3, 2009 - 4:01 pm
Don’t you think we need an increment by one each time we return from stack call, like
if(p->left){h1=height(p->left) + 1; // increment
#2 by Shrijeet on April 6, 2010 - 3:43 pm
No you dont need to increment, that is taken care by
this line: (number(p->left)+number(p->right)+1);
#3 by priyam das on November 10, 2009 - 2:47 pm
thanks very much….too good program
#4 by barun on January 2, 2011 - 11:00 am
static int maxht=0;
void height(int i,struct tnode *p)
{
if(p==NULL)
return();
height(i+1,p->left);
height(i+1,p->right);
if(maxht<i)
maxht=i;
}