## Flipkart Interview Question for Software Engineer / Developers

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

This is how I will do it
1) traverse till the node and use and array say if we move left store 0 and move right store 1
2) Now again traverse the tree, reading the array, if 0 then move right else move left

this will give us the mirror.

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

Time Complexity
O(logn) -> searching that node
O(logn) -> moving for the mirror
total : O(logn)
Space Complexity : O(logn)

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

O(logn) space and time in best case.

worst case it can be O(n) since a BST may not be balanced.

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

Node getMirrorNode(Node currNode , node mirrorNode , int data)
{
if(currNode == null || mirrorNode==null)
return null;

if(currNode->value == data)
return mirrorNode;

Node tmp;
tmp = getMirrorNode(currNode->left , mirrorNode->right , data);
if(tmp != null)
return tmp;

tmp = getMirrorNode(currNode->right , mirrorNode->left , data);
if(tmp != null)
return tmp;

}

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

call this function by passing , currNode = mirrorNode = root

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

I think mirror node of a node would always be its other sibling.
i.e. if this node is a left child of its parent then the mirror node would be the right child of its parent.
so..
if(node->right->data == data) return node->left;
else if (node->left->data == data) return node->right;
else{ tmp = getMirrorNode(node->left, data); if (tmp!= null) return tmp;
tmp = getMirrorNode(node->right, data); if (tmp!= null) return tmp;
}

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

Dude , you have 1 mirror to put. I a putting it in the middle of tree i.e at root node . For your case you have to put mirror in the middle of each node

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

No mirror can not be put in the middle of any node be it root or another node.
Tree Original Mirror Reflection
9 | 9
4 16 | 16 4
3 5 12 | 12 5 3

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

No mirror can not be put in the middle of any node be it root or another node.
Tree Original Mirror Reflection

``````9        |     9
4       16   | 16      4
3  5    12     |   12  5     3``````

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

So that is why the mirror of any given node is its sibling. Left or Right as applicable.

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

In the above example the mirror node of 5 is 12 ... and hence not a sibling.

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

@Loony: Check again, mirror node of 5 is 3 and not 12... 12's mirror node is empty or may be you try to draw a balanced tree with 3 nodes and see its reflection in mirror,

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

If sibling is consider as mirror node. wouldn't this Question be like "find the sibling of given input ? " LOL

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

Yes that is catch, I mean the question asked in a different way..
I may be wrong please some one help me if so

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

No, by the mirror node we mean .. If we compare the path from root node to the two nodes .. the path should be exactly opposite at each turn ... i.e. for every right move in the first path you should have a left move in the second path.

And that, in fact, is the answer .. find path and reverse it accordingly to find the mirror node.

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

yup u are correct

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

nice question!

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

No, by the mirror node we mean .. If we compare the path from root node to the two nodes .. the path should be exactly opposite at each turn ... i.e. for every right move in the first path you should have a left move in the second path.

And that, in fact, is the answer .. find path and reverse it accordingly to find the mirror node.

public Node mirrorNode(Node head, int data){

return null;

while(tmp!=null){
if(data==tmp.data)
return mirror;
if(data<tmp.data){
tmp = tmp.left
mirror=mirror.right
}else if(data>tmp.data){
tmp = tmp.right;
miror= mirror.left
}

}
return null;
}

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

is not simple to first find the path.. is it left right and left.. then mirror node must be right left and right..

but it might take a while to find the path :(

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

i think here you only need to exchange the link to find mirror

mirror(node *root)
{
if(root==NULL)
return;

node *temp;

mirror(root->left);
mirror(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;

}

i think it should work

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

Node * mirror(Node *n)
{
Node *temp = n;
while(n!=NULL && n->value!=value && temp!=NULL)
{
if(n->value < value)
{
n = n->right;
temp = temp->left;
}

else
{
n = n->left;
temp = temp->right;
}
}

if(temp!=NULL && n!=NULL)
return temp;

else
return NULL;

}

@vicky, iterative solution is better than recursive

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.