## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

``````void Print(struct node * root, int distance) //print node below given node ...
{
if(root == NULL || distance < 0)
return;
if(distance == 0)
printf("%d",root->data);
else
{
Print(root->left,distance -1);
Print(root->right,distance -1);
}
}
Void PrintAbove(struct node* root,int distance)  //print above node from given node ..
{
if(root == NULL || distance < 0)
return;
struct node * parent = NULL;
struct node* side = NULL;
parent = root->parent;
while(parent != NULL)
{
distance--;
if(distance == 0)
printf("%d",parent->data);
else if(root == parent->left)
{
Print(parent->right,distance);
}
else
Print(parent->left,distance);
if(parent->parent == NULL) //to check other side of root ...
side = root;
root = parent;
parent  = parent->parent;
}
if(distance >0)
{
if(side == root->left)
Print(root->right,distance);
else
Print(root->left,distance);
}

}``````

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

Normally you dont have the parent pointer in a binary tree

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

If BST parent can be easily found. For BT multiple pass required ...

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

whold not this be
Print(parent->right,distance-2);
Print(parent->right,distance);

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

This can be done in following way.
1# trace path from root to given node store that path in a linked list
or data structure where you can back trace it.

2# start from given node to find kth nodes in sub trees of given node.

3# start from given node. Back trace till kth node on root path. On each node occure in that path, find k-1, k-2, k-3...1th node respectively from current node on path.

This algo will work even if you don't have parent pointer. If parent pointer is given skip step 1# and back trace with parent pointer

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

@Cyrus in a way you are right but you will have to keep track of visited nodes. For instance

``````5
3              9
2        12     1      23
11  13                   21   99``````

Now if you want to print nodes at a distance 2 from 23 even with the method you described you will land into issues when you revisit an already visited node in your case you might also print 23 itself... Now the issue can be easily resolved by keep a track of visited nodes on which the searchNthNodeBelow() has been called or you can do something easier in this case as the only wrong answer will be the number itself(the node from where you have to start) and that too if the distance is even... so you can eleminate the source node from result if the distance !=0

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

this problem can occur only when we move upward from given node.
So we have to make sure when we move upward we only have to trigger function to find (k-i)th node for either left child or right child not the both.
thanks for specifying this point.

Comment hidden because of low score. Click to expand.
1
of 5 vote

int findD(node * root, int k)
{
if(!root)
return 0;
k--;
if(!k)
{
printf("-----%d----\n",root->data);
return 0;
}
findD(root->left,k);
findD(root->right,k);
return 0;
}

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

this code will print all nodes after kth level of the tree....

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

We are given a node in the binary tree call it A; and K is the distance given to us;
Now we start from the root node to find the node A,(if we are just given a value, even if we are given the node we need to do this). we set a global variable flag to be false; we start from root node with recursion, and as it is a binary tree, we have to travel in all the direction to find given node.once we find given node, we set flag to be tree, which indicate that the node is found and other recursion must stop here, and they do nothing, but the recursion in which we found the node A, we call a function ""findkthdistancenodes"" which has input as distance and the node from where it starts,
what the function do is written below, now while backtracing also return distance(updated one), in this recursion, every time we backtrace we reduce distance by one, if distance become zero, we print current node and stop backtracing, else call the function findkthdistancenodes(node->child(from which we are not tracing back this child may not be present then we don't), distance-1); now it is still possible that we reaches to root node, and still distance is not zero, then obviously after calling our function we stop.

what the function do is : it decrements distance by one every time when it change it's level, and it do the recursive call with all it's children with this newly updated distance, once distance become zero, it print current node.
I can also post the code here if anyone want

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

Am I missing something?

``````import java.util.List;

public class KNodes<T>{
public static class Node<T> {

T data;
Node<T> left;
Node<T> right;
public Node(T data) {
this.data = data;
left = null;
right = null;
}
}

public static <T> void findNodes(Node<T> node, int distance, List<Node<T>> result) {
if (node == null) return;
if (distance == 0) {

}
findNodes(node.left, distance-1, result);
findNodes(node.right, distance-1, result);
}

public static void main(String... args) {

Node<Integer> nodeTree = new Node<Integer>(20);
nodeTree.left = new Node<Integer>(5);
nodeTree.right = new Node<Integer>(10);
nodeTree.left.left = new Node<Integer>(1);
findNodes(nodeTree,2,res);
res.size();

}
}``````

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

1. treat this node as root and try to find all nodes with distance k
2. find the distance between this node and the real root such as d, the find all nodes with distance k-d to the real root.

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

an implementation of Cyrus's idea

bool findIt( queue<Node *> qu. Node *head, Node *n)
{
return false;
return true;
{
return true;
}
{
return true;
}

return false;

}

void search(Node *head, int num, int k)
{
return NULL;
if(num==k)
while(num<k)
{
}
}

void find(Node *head, Node *n, int k)
{
queue<Node *> qu;

if(!check)
return ;
Node *pre=n;

for(int i=1; i<=k;i++)
{
Node *tmp= qu.front();
qu.pop();
if(i==k)
{
count<<*tmp<<endl;
return;
}
if(pre==tmp->left)
{
pre=tmp;
search(tmp->left,i+1);
}
if(pre==tmp->right)
{
pre=tmp;
search(tmp->right,i+1);
}
}

}

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

/*

First I wrote a function to find out the nodes at distance k if the node is root.
Then in addition to these nodes i back track to the parents
If the node is the left child of the parent then I print out the elements that are k-2 away from the parent.
I decrement k as i move up following is the code
I tried it out it works
*/

``````void disrk(bst *head, int k) {
if(k<0)
return;
if (k == 0) {
cout << head->val << " ";
return;
}
cout << head->val << " ";
}

void disk(bst *head, int k) {
while (head->p && k > 0) {
cout << head->p->val << " ";
}
}
k = k - 1;
}
}``````

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

Here is my solution. It finds the nth node and calculate the distance at the same time.

``````//Find kth distance of given node
public class TestDistranceToNode {

public static void main(String[] args) throws Exception {

Node root = new Node(null, 21);
Tree tree = new Tree(root);

distance(tree.root,20, 6, -1);
}

private static int distance(Node node,int n, int D, int d) {

if (node == null) {
return -1;
}

if (d >-1) {

if (node.isViewed) {
return d;
}
}

if (node.val != n && d<0) {
d =  distance(node.left, n, D, d);

if (d < 0) {
d =  distance(node.right, n, D, d);
}

if (d<0)
return d;

} else if (node.val == n){
d = 0;
}

node.isViewed = true;
node.distance = d;

distance(node.left, n, D, d+1);
distance(node.right, n, D, d+1);

if (D == d) {
System.out.println(node.val);
}

return d+1;
}
}``````

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

``````static void searchNodeAtDist(TreeNode n, int dist, ArrayList<TreeNode> list)
{
if(n!= null && dist!=0)
{
searchNodeAtDist(n.left, dist-1, list);
searchNodeAtDist(n.right, dist-1, list);
}
if(n!=null && dist==0)
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

What about a breadth first search? Something like print level by level ... until you reach the k-th level. Stop and print the k-th level.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This would be the implementation of the breadth-first search mentioned above

``````void nodesAtDistanceK (node *root, int k) {
int i;
queue<node> nodeQueue;

nodeQueue.push(root);

for (i = 0; i < 2^k-1; i++) {

node temp = nodeQueue.pop();
nodeQueue.push(temp->left);
nodeQueue.push(temp->right);
}

//Print all the elements of nodeQueue to get the nodes at depth k

}``````

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.