## Amazon Interview Question

Country: India

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

If we're dealing with a tree, just use a BFS and break on level k.

O(E+V)

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

Why is this a tree?

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

@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.

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

It would make an interesting problem if data structure was a binary tree with no parent pointers.

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

Of course BFS :)

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

#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);

}

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

its a generic question, might not be binary tree and that too may not be the root of a binary tree.

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.