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

- mustafa khaleefuddin qureshi July 28, 2011 | Flag Reply
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.

- NeoX April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Ravi June 26, 2010 | Flag Reply
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.

- kaustubhonline15 July 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Praveen August 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- praveenk434 August 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Harish July 03, 2011 | Flag


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