## Amazon Interview Question for Development Support Engineers

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

``````int distance(node *start)
{
stack<node* > leftpreorder;
stack<node* > rightpreorder;
int flag = 0;
int counter = 0;
int leftmost = 0;
node *ptr = start;
while(start->left != NULL || start->right != NULL)
{
if(flag == 0)
leftmost = counter;
if(start->left)
{
leftpreorder.push(start);
flag = 0;
counter++;
start = start->left;
}
else if(start->left == NULL)
{
leftpreorder.push(start);
start = start->right;
counter++;
flag = 1;
}
}
flag = 0;
counter = 0;
int rightmost = 0;
while(ptr->left != NULL || ptr->right != NULL)
{
if(flag == 0)
rightmost = counter;
if(ptr->right)
{
rightpreorder.push(ptr);
flag = 0;
counter++;
ptr = ptr->right;
}
else if(ptr->right == NULL)
{
rightpreorder.push(start);
ptr = ptr->left;
counter++;
flag = 1;
}
}
return leftmost+rightmost+2;
}``````

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

the conditions inside your while loops should be &&

Otherwise, for instance, when start->left is null, the while loop exits before you can finish heading down to the leftmost child of the right subtree.

Same for the rightmost leaf one.

Also, anyone would think that for the leftmost and rightmost nodes you simply traverse down root->left-> left->left-> ....
and
root->right->right...

so far but your solution raises a good point of ambiguity. What do we classify as the leftmost/rightmost leaf node here

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

could you please elaborate your question thru example

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

I assume, the question is to find the number of terminal nodes.

Quick solution came to my mind is to traverse the tree and place a static counter on left-right null node.

Please comment.

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

mine solution goes here ..

func()
{
intitial leftdis=0 rightdis=0

temp =root;
while(temp->left || temp ->right)
{
while(temp->left)
{
temp = temp -> left
leftdis++
}
if(temp->right&& ! temp->left)
{
temp = temp ->right
leftdis++
}
}

temp =root;
while(temp->left || temp ->right)
{
while(temp->right)
{
temp = temp -> right
rightdis++
}
if(! temp->right&& temp->left)
{
temp = temp ->left
rightdis++
}
}
finaldis = leftdis+rightdis -1
}

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

0---------------0-----------0-----0
| |
| 0
| |
| 0------0----0----0
|
0------0-----0
| |
| 0
0------0
|
0------0-----0
| |
0 0
|
0
|
0
|
0
Please note that horigental line tells right child and vertical (down) is left child.

I think this algo will not give correct answer for this tree.

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

0---------------0--------0-----0
|...............|
|...............0
|...............|
|...............0---0---0----0----0
|
0------0-----0
|......|
|......0
|
0------0
|
0------0-----0
|......|
0......0
.......|
.......0
.......|
.......0
.......|
.......0
please ignore previous one as white space is ignored...
Please note that horigental line tells right child and vertical (down) is left child.
dots are used for placing at right place
I think this algo will not give correct answer for this tree.

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

leftdis and rightdis initially should be set to 1

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

Nice Solution

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

Can you give the defination of distance between two leaf nodes.

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

1)Find out the left and rightmost leaves
2)do BFS,and if a terminal node is reached which is not either,increment count by 1

any thoughts?

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

This code does not work for above tree explained by Anonymous

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

Do a pre-order and reverse postorder tranversal and subtract the nodes coming first.

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

Question re-framed for better understanding:
Find the diameter of a tree.

Solution:

``````void diameter(Tree* t, int& depth, int& dia)

{

if (t == NULL) {

depth = 0;

dia = 0;

return;

}

int leftDepth, rightDepth;

int leftDiameter, rightDiameter;

diameter(t->leftChild, leftDepth, leftDiameter);

diameter(t->rightChild, rightDepth, rightDiameter);

depth = max(leftDepth, rightDepth) + 1;

dia = max(leftDiameter, rightDiameter, leftDepth + rightDepth + 1);

}``````

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

sorry! seems the "space key" creates a mess sometimes. some bug with website :-(

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

googler, your solutions seems okey to me as the question really asks about finding the diameter of the tree.

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

It is not the diameter of the tree.. because, diameter is the distance between 2 deepest leaves.. These 2 leaves, need not be the leftmost node and right most node..

The solution is to do DFS and going to the leftmost node first at each node. As soon as the left most node is reached, we make a note of the depth.

Then repeat DFS from the root, now going to the rightmost node at each node. As soon as a leaf is reached, we make a note of the depth.

Add them.

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

yes, you're right, its not the dia.

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

yes anonymous is right well do dfs on root to reach leftmost and then start again on root to reach rightmost and add depths in both cases ...

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

The diameter of a tree is the LONGEST distance between ANY two nodes (and hence the distance between two deepest leaves).
So, the diameter is not necessarily the distance between the left-most and the right-most leaves always.

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

To find the diameter of a BST:
------------------------------
1) Find the distance between the root to all the leaves (Calculate all the root-leaf-distances).
2) All the top two highest root-to-leaf distances. This is the longest distance between any two nodes in the BST. Hence, this sum is the diameter of the tree.

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

``````small changes in Manish's code .... @Manish, please check whether ur code works for the below given tree

1
10(left of 1)
14(left of 10)
16(left of 16)
17(right of 16)
18      20(right of 17)
19 (left of 18)

i made some changes in ur code ... please check whether it will work now ....
the idea is the first node which u encounter which has both a left and right branch will be the node that connects the left branch and right branch while computing the distance between leftmost leaf and rightmost leaf

func()
{
intitial leftdis=0 rightdis=0
temp =root;
while(temp->left || temp ->right)
{

if(temp->left && temp->right )
flag = 1;

if(temp->left)
{
temp = temp -> left
if(flag == 1)  leftdis++;
}

if(temp->right&& ! temp->left)
{
temp = temp ->right
if(flag = = 1) leftdis++;
}
}

temp =root;
while(temp->left || temp ->right)
{
if(temp->left && temp->right )
flag = 1;

if(temp->right)
{
temp = temp -> right
if(flag == 1)  rightdis++;
}

if(temp->right&& ! temp->left)
{
temp = temp ->left;
if(flag = = 1) rightdis++;
}

}
finaldis = leftdis+rightdis
}``````

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

Nice solution man

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

void longestdistance(node **head)
{
node *p=*head;
int countleft=1,countright=1;
while(p->left!=NULL || p->right!=NULL)
{
while(p->left!=NULL)
{
p=p->left;
countleft++;
}
if(p->left==NULL && p->right!=NULL)
{
p=p->right;
countleft++;
}
}
p=*head;
while(p->left!=NULL || p->right!=NULL)
{
while(p->right!=NULL)
{
p=p->right;
countright++;
}
if(p->right==NULL && p->left!=NULL)
{
p=p->left;
countright++;
}
}
cout<<countleft<<" "<<countright<<endl;
cout<<(countleft+countright-1);
}

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

this question is pretty dumb.
have a counter and keep traversing to the left increasing the counter each time till you hit NULL, similarly for the right child. just add these two values and you are done.
this is my code in CPP

``````int getLeftmostRightmostLeafDistance(Node *head) const throw() {
if (head == NULL) {
return 0;
} else {
Node *temp = head;
int leftmost = 0;
int rightmost= 0;
while (temp->left != NULL) {
leftmost++;
temp = temp->left;
}
// reset temp to head
temp = head;
while (temp->right != NULL) {
rightmost++;
temp = temp->right;
}
cout << "extreme leaves distance= " << leftmost+rightmost << endl;
}
}``````

Tested OK !

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

@above .. you are dumb ..he solutions is right .. in question they asked for the right most and the leftmost ..

in your example rightmost node would be none other than the root itself... u just need to find the distance between the leftmost node to the root ..thats all...

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More