Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Diameter is the maximum distance from one leaf node to another.
It is the maximum path length which can either pass through root of the subtree at that point or may not , as it may entirely lie in the left/right subpart of the tree. So basically it is the maximum of left-diamter, right-diameter and the height of the tree(case when diameter passes through the current root).
diamter = max(height ,max (leftDiameter , rightDiamter) )
pass the parameter of height to avoid extra calls during recursion and then update the current height. Return the maximum of diamter from that node.
int diameter(node * root, int *height){
if(root == NULL) { height = 0; return 0;}
int leftHeight =0 , rightHeight = 0;
int leftDiamter = diameter(root->left , &lh);
int rightDiameter = diameter(root->right, &rh);
*height = max(leftHeight, rightHeight) + 1 ;
return max( (max ( leftDiamter , rightDiameter ) , height );
}
Time Complexity = O(n) // as only 1 visit to all the nodes.
int dia(node *r,int *diam)
{
if(r==NULL)
return 0;
cout<<"in\n";
int ld,rd;
ld=rd=0;
int lh,rh;
lh=rh=0;
lh=dia(r->left,&ld);
rh=dia(r->right,&rd);
*diam=imax(ld,rd,lh+rh+1);
return lh>rh?lh+1:rh+1;
}
// it returns height of root and diameter can be found in the argument (pass by pointer) diam
/* initial call should be
int diam=0;
dia(root,&diam);
cout<<diam;
*/
int diameter(struct node * tree)
- k2 April 14, 2012{
/* base case where tree is empty */
if (tree == 0)
return 0;
/* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);
/* get the diameter of left and right sub-trees */
int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);
/* Return max of following three
1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}