Program to Find the Maximum Depth or Height of a Tree

For below tree maximum depth or height is 3.

Algorithm :

1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e.,
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e.,
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,
                             max depth of right subtree)
                             + 1
     (d) Return max_depth

Code :

int maxHeight(struct node* node)
{
   if (node==NULL)
       return 0;
   else
   {
       /* compute the depth of each subtree */
       int lDepth = maxHeight(node->left);
       int rDepth = maxHeight(node->right);

       /* use the bigger one */
       if (lDepth > rDepth)
           return(lDepth+1);
       else return(rDepth+1);
   }
}

Time Complexity: O(n)

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*