## Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

Detailed description of the above solution is here:

crackinterviewtoday.wordpress.com/2010/03/11/diameter-of-a-binary-tree/

Comment hidden because of low score. Click to expand.
0

gud explaination here

Comment hidden because of low score. Click to expand.
0

No doubt good explanation.
However they are recursively traversing the tree twice.
Same recursion, gathering different data. Should be able to do it in one recursion.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int 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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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/

Comment hidden because of low score. Click to expand.
0

int diameter (Node *root) {
if(root){
int d1 = 1+diameter(root->left);
int d2 = 1+diameter(root->right);
if( d1+d2 > max_dia ) {
max_dia = d1+d2;
}
return max( d1, d2 );
}
return 0;

}
int max(int d1, int d2){
if (d1 > d2 ) return d1;
else if(d2 > d1) return d1;
else return d1;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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)))

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

For and O(n) algo visit "http: // t.co / lum8dAM"

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.