What is the diameter of a binary tree?? I was asked this question in second round of onsite interview. The interviewer first asked me to flip the adjacent nodes of a linked list. He asked if I know the question and since the question seemed easy and doable, I said I know the algorithm and can be done. So he changed the question and asked me to find the diameter of binary tree. I did not know what is the diameter of binary tree. So he helped me to come up with the algorithm and I coded it. Diameter of binary tree is the length of the longest path present in a binary tree.
int max(int a, int b)
{
return (a >= b)? a: b;
}
int maxDepth(struct bTreeNode *root)
{
if(root == NULL)
{
return 0;
}
else
{
int ld = maxDepth(root->lNode);
int rd = maxDepth(root->rNode);
if( ld > rd)
return ld+1;
else
return rd+1;
}
}
int diameter(struct bTreeNode *root)
{
if(root == NULL)
{
return 0;
}
else
{
int ld = diameter(root->lNode);
int rd = diameter(root->rNode);
int lh = maxDepth(root->lNode);
int rh = maxDepth(root->rNode);
return max(lh + rh + 1, max(ld, rd));
}
}
Source : http://geeksforgeeks.org/?p=5687
Its also important to come up with test cases, to show that your code is working. For this problem there are three cases that needs to be tested. You need to give inputs such a way that you get all 3 possible answers for the respective input i.e. lh+rh+1 or ld or rd. .
ps: I am posting only rough code and I am in no way responsible if the code is wrong. I am also giving other links which have posted proper code and I felt there is no point in writing the same code here. Please refer to those sites.
Thursday, June 24, 2010
Find the Diameter of a binary tree?
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment