Amazon Interview Question
Software Engineer / DevelopersTeam: 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