Amazon Interview Question
Country: India
@oOZz
I should have said graph, and assumed the problem was modeled as such. It was a bad assumption to say "tree" rather than "graph".
It could also be any other data structure where an element is referred to as a "node." The problem itself doesn't specify a data structure.
#include<stdio.h>
#include<stdlib.h>
struct BT
{
struct BT *l;
struct BT *r;
int data;
};
void findKthnodes(struct BT *root,int level,int k)
{
if(!root)
return;
if()
if(level==k)
printf("[%d]\t",root->data);
findKthnodes(root->l, level+1,k);
findKthnodes(root->r,level+1,k);
}
struct BT *nn(int d)
{
struct BT *root=(struct BT *)malloc(sizeof(struct BT) );
root->l=NULL;
root->r=NULL;
root->data=d;
return root;
}
main()
{
struct BT *rt=nn(5);
rt->l=nn(45);
rt->r=nn(565);
rt->l->l=nn(453);
rt->l->r=nn(33);
rt->r->l=nn(656);
rt->r->r=nn(55);
rt->r->l->r=nn(56);
int level=0;
int k=2;
findKthnodes(root,level,k);
}
If we're dealing with a tree, just use a BFS and break on level k.
- zbesst June 17, 2013O(E+V)