## Flipkart Interview Question for Software Engineer / Developers

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

1. search for the node in the tree keeping track of all the nodes in the path. Use stack for storing the nodes.

``````int searchanode(Node *root, Node *search)
{
if(root == NULL) return 0;

s.push(root);
if(root == search) { return 1;}
int found = searchanode(root->left, search) || searchanode(root->right, search);
if(!found)s.pop();
return found;
}``````

2. pop first element of the stack, which is the node itself. call recursive routine to print all nodes at distance k below this node.

``````void printknebors( Node *curr, int k)
{
if(!curr) return;
if( k == 0 ) {
printf("%d ", curr->val);
return;
}
printknebors(curr->left, k-1);
printknebors(curr->right, k-1);
}``````

3. pop remaining elements, that is, each parent, keep track of the previous child(previously popped element) and get its sibling.
call above recursive routine to print elements at k-2 distance from the sibling node.

``````void printknebors(int k)
{
Node *curr = NULL;
while(!s.empty() && k)
{
Node *parent = s.top(), *temp = NULL;
s.pop();
if(!curr) { printknebors(parent, k); }
else
{
if(k==1) { printf("%d ", parent->val); }
else {
if(curr == parent->left) temp = parent->right;
else temp = parent->left;
printknebors(temp, k-2);
k--;
}
}
curr = parent;
}
}``````

time: O(n) to find the element, O(2^k) for the 2^k+2^(k-2)+2^(k-3)+.. +1 neighbors

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

This is the same question as, give a binary tree and a node, find all the nodes which are at a distance k from the given node in the tree. Distance is just number of links in any direction. I think the steps should be following:
1) First find the distance of given node N from root. Lets say its d.
2) Finding nodes at a distance k from N going down is easy. Just traverse the tree with N as root and print all nodes at level k.
3) Finding nodes at a distance k from N going up is somewhat tricky, We start with nodes at distance d-k from root and print them out, then nodes at d-k-1 and print nodes at distance 1 going down and so on.
I hope you get the idea.

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

Do BFS, All nodes at height h is the required answer!

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

printAllNth(Tree root, int n){

if(root==null)return;
if(n==0){
print(root.data)
return;
}
printAll(root.left, --n)
printAll(root.right, --n)
}// considering root level is 0 height.

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

I guess this is the answer to find all the nodes which are at given length from root node. Is this is the question. Some one please clarify the question, it is not clear to me.
Thanks.

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

Small correction.

printAllNth(Tree root, int n){

if(root==null)return;
if(n==0){
print(root.data)
return;
}
printAll(root.left, n-1)
printAll(root.right, n-1)
}// considering root level is 0 height.

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

I guess the question meant all distances upto length distance from any given node. So it need not be from the root node. So above solution will not work

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.