Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
1) Scan the tree to look for the node and push all parent nodes encountered in the path to a stack S
2) Write a function to find nodes at K distance which are child of this node (simple DFS). Lets call that function kChild(node)
3) Now pop the parent of the node and find out the k -1 distance child nodes of it.
4) Repeat the process till the stack is empty.
void findbelow(struct tnode *root,int level,int k)
{
if(root==NULL)
return;
if(level==k)
{
printf("%d\t",root->val);
return;
}
findbelow(root->left,level+1,k);
findbelow(root->right,level+1,k);
}
void findabove(struct tnode *root,struct tnode *node,int level,int k)
{
static int vector=0;
if(root==NULL)
return;
findabove(root->left,node,level+1,k);
findabove(root->right,node,level+1,k);
if(root==node)
vector = vector | 1<<level;
if(vector & 1<<(level+k))
{
vector = vector ^ 1<<(level+k);
printf("%d\t",root->val);
}
}
Most probably this qus is for tree/graph right?
- PKT March 23, 2014