Amazon Interview Question
Software Engineer / Developersint diameter = 0;
int findDiameter(struct tree * node)
{
int dim ,l_len,r_len;
/* If null node came then return 0 */
if(node == 0)
return 0;
/* Initialize all the temp length variables by 0 */
dim = l_len = r_len = 0;
/* Recursive call for left & right subtree */
l_len = findDiameter(node->left);
r_len = findDiameter(node->right);
/* Calculate the depth at this level */
dim = r_len + l_len + 1;
/* If the current level diameter is bigger then previous */
/* Then save the current diameter as biggest one */
if(dim > diameter)
diameter = dim;
/* Return the depth, till current node */
return (MAX(l_len,r_len) + 1);
}
public int diameterOfBinaryTree(Node node)
{
if (node == null)
{
return 0;
}
int leftHeight = heightOfBinaryTree(node.left);
int rightHeight = heightOfBinaryTree(node.right);
int leftDiameter = diameterOfBinaryTree(node.left);
int rightDiameter = diameterOfBinaryTree(node.right);
return Math.max(leftHeight + rightHeight + 1,
Math.max(leftDiameter, rightDiameter));
}
working code...visit:
h**p://crackinterviewtoday.wordpress.com/2010/03/11/diameter-of-a-binary-tree/
void traverse(struct node *t, int depth, int *first, int *second)
{
if(t==NULL) return;
if(t->left==NULL && t->right==NULL) { //Hit a leaf
if(depth>*first) {
*second = *first;
*first = depth;
}
else if(depth<*first && depth>*second) *second = depth;
return;
}
traverse(t->left, depth+1, first, second);
traverse(t->right, depth+1, first, second);
}
int main()
{
int *first, *second;
*first = *second = 0;
traverse(root, 1, &first, &second);
print *first + *second;
}
// Guys, This question threw me out from AMAZON, second interview round.......
but i make it on next day.......
// Assume a function height_tree(node *root) will
//return sum of height of left sub tree and height of right sub tree+2;
//I am counting no of edges...
int tree_bredth(node *root)
{
int i,j,k;
i = 0;
j = 0;
k = 0;
if(root = NULL)
return(0);
i = height_tree(root->left);
j = height_tree(root->right);
k = i+j+2;
return(max(k,tree_bredth(root->left),tree_bredth(root->right)))
}
check this
int TreeDiameter(Tnode *root)
{
static int max,diameter;
static Tnode *tmp=NULL;
if(root==NULL)
return 0;
if(tmp==NULL)
tmp=root;
int leftmax=TreeDiameter(root->left);
int rightmax=TreeDiameter(root->right);
if(diameter<(leftmax+rightmax))
diameter=leftmax+rightmax;
if(leftmax >= rightmax)
{
max=leftmax;
}
else
{
max=rightmax;
}
if(tmp==root)
return diameter;
return 1+max;
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int Diameter(struct node *R,int *height)
{
int ld=0;
int rd=0;
int rh=0;
int lh=0;
if(R==NULL)
{
*height=0;
return 0;
}
ld=Diameter(R->left,&lh)+1;
rd=Diameter(R->right,&rh)+1;
*height=(lh>rh?lh:rh)+1;
return(max(lh+rh+1,max(ld,rd)));
}
int diaMeter (struct node* node)
{
if (node == NULL)
return 0;
/* get the height of left and right sub-trees */
int lheight = maxDepth(node->left);
int rheight = maxDepth(node->right);
/* get the diameter of left and right sub-trees */
int ldiameter = diaMeter(node->left);
int rdiameter = diaMeter(node->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));
}
Python code
## General binary tree node class. @property is not useful right now.
class Node(object):
def __init__(self, value=None, left=None, right=None):
self.__left = left
self.__right = right
self.__value = value
@property
def right(self):
return self.__right
@right.setter
def right(self, value):
self.__right = value
@right.deleter
def right(self):
del self.__right
@property
def left(self):
return self.__left
@left.setter
def left(self, value):
self.__left = value
@left.deleter
def left(self):
del self.__left
def get_diameter(node):
if not node:
return (0, 0)
if not isinstance(node, Node):
raise Exception(" Invalid param type ")
(left_height, left_diameter) = get_diameter(node.left)
(right_height, right_diameter) = get_diameter(node.right)
current_diameter = 0
if node.right and node.left:
current_diameter = left_height + right_height + 1
return (max([left_height, right_height]) + 1, max([left_diameter, right_diameter, current_diameter]))
# Case 2: Diameter is not through root
#
# 1
# 2
# 4 5
# 8
# 9
root = Node(1)
root.left = Node(2)
root.left.left = Node(4)
root.left.right = Node(5)
root.left.left.left = Node(8)
root.left.left.left.left = Node(9)
print "case 1 : Height : %s Diameter : %s" % get_diameter(root)
# case 2: Diameter through root
# 1
# 2 3
# 4 5 6 7
# 8 10
# 9 11
root.right = Node(3)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(10)
root.right.left.right.left = Node(11)
print "case 2 Height : %s Diameter : %s" % get_diameter(root)
Detailed description of the above solution is here:
- Anonymous March 30, 2010crackinterviewtoday.wordpress.com/2010/03/11/diameter-of-a-binary-tree/