Finding maxdepth in binary search tree

Here is the code of binary search tree

#include<stdio.h>
#include<conio.h>
#include"malloc.h"

struct node
{
    int data;
    struct node* left;
    struct node* right;
};
int size(struct node* n)
{
    if(n==NULL)
       return 0;
    else
       return (size(n->left)+1+size(n->right));
}

int maxdepth(struct node* n)
{
    int ldepth,rdepth;
    if(n==NULL)
    {
       return 0;
    }
    else
    {
       ldepth=maxdepth(n->left);
       rdepth=maxdepth(n->right);
       if(ldepth>rdepth)
          return (ldepth+1);
       else
          return (rdepth+1);
    }
}

int lookup(struct node* node,int target)
{
    if(node==NULL)
       return 0;
    else if(target==node->data)
       return 1;
    else if(target<node->data)
       return(lookup(node->left,target));
    else
       return(lookup(node->right,target));
}

struct node* newnode(int data)
{
     struct node* newnod=(struct node*)malloc(sizeof(struct node));
     newnod->data=data;
     newnod->left=NULL;
     newnod->right=NULL;
     return newnod;
}

struct node* insert(struct node* root,int targe开发者_StackOverflow社区t)
{
    if(root==NULL)
        return(newnode(target));
    else if(target<=root->data)
        root->left=insert(root->left,target);
    else 
        root->right=insert(root->right,target);
    return root;
}

void main()
{
    int result,s,max;
    struct node* newnode=NULL;
    clrscr();
    newnode=insert(newnode,2);
    newnode=insert(newnode,3);
    newnode=insert(newnode,4);
    max=maxdepth(newnode);
    printf("maxdepth %d\n",max);
    s=size(newnode);
    result=lookup(newnode,3);
    printf("size %d\n",s);
    printf("%d",result);
    getch();
}

When I runs this program . I get maxdepth has 3.

If I change the maxdepth function as

int maxdepth(struct node* n)
{
    int ldepth,rdepth;
    if(n==NULL)
    {
        return 0;
    }
    else
    {
        ldepth=maxdepth(n->left);
        rdepth=maxdepth(n->right);
        if(ldepth>rdepth)
            return (ldepth);
        else
            return (rdepth);
    }
}

I get the maxdepth value as 0. what is the problem? I couldn't not figure it out?

You are not counting the current node, so a +1 is needed.

      {
        ldepth = maxdepth(n->left);
        rdepth = maxdepth(n->right);

        if(ldepth > rdepth)
          return ldepth + 1;
        else
          return rdepth + 1;
      }

Without the +1 maxdepth always will return 0. Because ldepth and rdepth will always be 0.

An example of a tree with 3 nodes:

   A
 /   \
B     C

Now you call maxdepth(A), this will do: ldepth = maxdepth(B); rdepth = maxdepth(C);, then maxDepth(B) will do: ldepth = maxdepth(null); rdepth = maxdepth(null); /* ldepth and rdepth are now 0 */, so maxDepth(B) will return as a result 0. Similar maxDepth(C) will return 0. You will do then:

if(ldepth > rdepth)
  return ldepth;
else
  return rdepth;

But both ldepth and rdepth are 0, so rdepth will be returned which is 0. Finally maxdepth(A) will return 0 as a result.

That's why +1 is needed.

Let's look at an example tree:

    __A__
   /     \
  B       C
 / \     / \
D   E   F   G

In this tree, we're perfectly balanced so we're not going to worry about which is the taller subtree at each node (they're the same height). So we'll just calculate the height using the left branches.

What is the height of the tree? It's the height of A.

What is the height of A? It's one plus the height of B.

In turn, the height of B is one plus the height of D, and the height of D is one plus the height of D's left branch, which is zero.

So total height is 1 + 1 + 1 + 0 = 3.

So the algorithm in this (simplified) case is:

def height (node):
    if node is null:
        return 0
    return 1 + height (node.left)

And that's why your recursive height function has to add one at each level. If instead you add 0 (which is what your second code segment is doing), you switch from getting 1 + 1 + 1 + 0 = 3 to getting 0 + 0 + 0 + 0 = 0.

If you modify the algorithm above to take into account different sizes of subtrees, you basically get your first code segment, which works fine:

def height (node):
    if node is null:
        return 0
    leftheight = height (node.left)
    rightheight = height (node.rigth)
    return 1 + max (leftheight, rightheight)