## Amazon Interview Question

Software Engineer / Developers**Team:**SDE

**Country:**India

**Interview Type:**In-Person

Find the depth of the given node (say d). find the children from the root upto k-d levels leaving the branch that is towards the given node. traverse one step ahead towards the given node and now find the children upto k-d+1 levels leaving the branch that is towards the given node.

Do it until the given node is reached. Then find children at k levels below the given node.

Note: If k<d, traverse until d-k towards the given node and do the same

Complexity: O(k.d)

#include <stdio.h>

#include <stdlib.h>

struct node

{

int data;

struct node *left;

struct node *right;

};

int max(int a, int b)

{

return a > b ? a : b;

}

int height(struct node *node)

{

if(node == NULL)

return 0;

return 1 + max(height(node -> left), height(node -> right));

}

void printkdistantdown(struct node *root, int k)

{

if(root == NULL)

return;

if(k == 0)

{

printf("%d ", root -> data);

return;

}

printkdistantdown(root -> left, k-1);

printkdistantdown(root -> right, k-1);

}

void printkdistantup(struct node *node, int k, struct node *root)

{

int h1 = height(node);

int h2 = height(root);

printkdistantdown(root, h2-h1-k);

}

struct node* newNode(int data)

{

struct node* node = (struct node*)

malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

}

/* Driver program to test above functions*/

int main()

{

/* Constructed binary tree is

1

/ \

2 3

/ \ /

4 5 8

*/

struct node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

root->right->left = newNode(8);

printkdistantdown(root, 2);

printf("\n");

printkdistantup(root -> left -> left, 1, root);

}

Step1. Convert the BST in a sorted Array

- Anonymous February 05, 2012Step2. Find the index of given node (say i)

Setp3 print all elements from i-k to i+k