Height of the binary tree!


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.

About these ads
  1. #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);

  2. #3 by priyam das on November 10, 2009 - 2:47 pm

    thanks very much….too good program

  3. #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;
    }

  1. What is a Binary Tree? « Encrypt3d
  2. What are Trees? « Encrypt3d
  3. How to count number of nodes in a Binary Search Tree? « Encrypt3d

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: