Thursday, Aug 16th

Last update12:59:40 PM GMT

Write a C program to find the depth or height of a tree.

Write e-mail
The most efficient solution to this problem is recursive. We start with the root, and calculate the height of left and right sub-tree in recursive manner. The max of these two heights is one less than the height of this tree.

tree_height(mynode *p)
{
      if(p==NULL)return(0);
      if(p->left){</code>
<code>            h1=tree_height(p->left);</code>
<code>      }
      if(p->right){</code>
<code>            h2=tree_height(p->right);</code>
<code>      }
      return(max(h1,h2)+1);
} 
</code>



The degree of the leaf is zero. The degree of a tree is the max of its element degrees. A binary tree of height n, h > 0, has at least h and at most (2^h -1) elements in it. The height of a binary tree that contains n, n>0, elements is at most n and atleast log(n+1) to the base 2.

Log(n+1) to the base 2 = h

n = (2^h - 1)

Share this post



Web Hosting