Amazon Interview Question Development Support Engineers
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
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
}
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.
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.
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);
}
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.
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.
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
}
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);
}
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 !
- Manish Agarwal October 04, 2009int 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; }