Thursday, October 31, 2013

Diameter of a tree (longest leaf to leaf path)

I  do  not  know  what  was  GeeksforGeeks  algorithm  for  this  question.  I  did  not  get  a  bit  of  that.
But  this  is  my  code  which  has  passed  all  the  cases  from  interviewstreet.com.  You  can  yourself check   second  question  in   the  link  below

https://www.interviewstreet.com/recruit/test/start/sample


Here  is  my  code..  Hope  it  is  easily  understood

In  this  we  are  taking  that  both  the  leaves  have  common  source (which  may  be  root  or  any  other)
which  is  passed  into  the  function diameterOfTree()

Leaf  to  Leaf  path  from  that  node will  be  1+lh+rh

And  maximum  of  all  that  is  calculated

int maximum(int a,int b)
{
    if(a>=b)
        return a;
    else
        return b;
}  


int max=0;

int height(node* root)
{
    if(root!=NULL)
    {  
    int lh=height(root->left);
    int rh=height(root->right);
 
    return 1+maximum(lh,rh);
    }
    return 0;
}




int diameterOfTree(node * root)
{
    if(root!=NULL)
    {
    int temp=1+height(root->left)+height(root->right);
        if(temp>max)
            max=temp;
    diameterOfTree(root->left);
    diameterOfTree(root->right);
    }
    return max;
}

No comments:

Post a Comment