Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
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
@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
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;
}
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
Am I missing something?
import java.util.List;
import java.util.LinkedList;
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) {
result.add(node);
}
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);
List<Node<Integer>> res = new LinkedList<Node<Integer>>();
findNodes(nodeTree,2,res);
res.size();
}
}
an implementation of Cyrus's idea
bool findIt( queue<Node *> qu. Node *head, Node *n)
{
if(head==NULL)
return false;
if(head==n)
return true;
if(findIt(qu,head->left,n))
{
st.push(head->left);
return true;
}
if(findIt(qu,head->right,n))
{
st.push(head->right);
return true;
}
return false;
}
void search(Node *head, int num, int k)
{
if(head==NULL)
return NULL;
if(num==k)
cout<<head<<endl;
while(num<k)
{
search(head->left,num+1,k);
search(head->right,num+1,k);
}
}
void find(Node *head, Node *n, int k)
{
queue<Node *> qu;
bool check=findIt(st,head,n);
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);
}
}
}
/*
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 << " ";
if (head->l)
disrk(head->l, k - 1);
if (head->r)
disrk(head->r, k - 1);
}
void disk(bst *head, int k) {
disrk(head, k);
while (head->p && k > 0) {
cout << head->p->val << " ";
if (head->p->r == head) {
disk(head->p->l, k - 2);
}
if (head->p->l == head) {
disk(head->p->r, k - 2);
}
k = k - 1;
head=head->p;
}
}
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);
tree.addNode(root, 13);
tree.addNode(root, 37);
tree.addNode(root, 5);
tree.addNode(root, 9);
tree.addNode(root, 19);
tree.addNode(root, 18);
tree.addNode(root, 20);
tree.addNode(root, 29);
tree.addNode(root, 35);
tree.addNode(root, 54);
tree.addNode(root, 72);
tree.addNode(root, 46);
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;
}
}
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
}
- MI January 20, 2013void 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); } }