MCN Professionals | Interview Question of the day
To receive one interview question in your mailbox daily, please subscribe to "A Question A Day" at MCN Professionals home page.-----------------------------------------------------------------------------------------------------------------------------------------
Today's Question:
Diameter of a tree is the longest path (Number of nodes) between two leaf nodes of the tree. It is also called width of the tree. For example, diameter of the below tree is 6 (red color nodes form part of the diameter
A
/ \
B C
/ / \
D E F
\
G
Note that the diameter may not, necessarily include the root of the tree.
Solution:
At any given time the diameter of the tree (or sub-tree) is the largest of the following:
- Diameter of Left sub-tree (does not include current root in diameter)
- Diameter of Right sub-tree (does not include current root in diameter)
- The longest path that goes thru the root of tree (Height of LST + Height of Right Subtree + 1)
Code:
/* Returns the diameter of a binary tree */
int diameter(Node * root)
{
if (root == 0)
return 0;
// Get the height of left & right sub-trees
int lh = height(root->lptr);
int rh = height(root->rptr);
// Diameter of left and right subtrees recursively
int ld = diameter(root->lptr);
int rd = diameter(root->rptr);
return max( (lh+rh+1), ld , rd );
}
// Function to compute the height of a Binary tree
int height(Node* root)
{
if(root == NULL)
return 0;
return ( 1 + max(height(root->lptr), height(root->rptr) ) ;
}
-----------------------------------------------------------------------------------------
Interview Questions Archive:
To see all the questions in the category click
here...