Flipkart Interview Question
Software Engineer / DevelopersThis is the same question as, give a binary tree and a node, find all the nodes which are at a distance k from the given node in the tree. Distance is just number of links in any direction. I think the steps should be following:
1) First find the distance of given node N from root. Lets say its d.
2) Finding nodes at a distance k from N going down is easy. Just traverse the tree with N as root and print all nodes at level k.
3) Finding nodes at a distance k from N going up is somewhat tricky, We start with nodes at distance d-k from root and print them out, then nodes at d-k-1 and print nodes at distance 1 going down and so on.
I hope you get the idea.
printAllNth(Tree root, int n){
if(root==null)return;
if(n==0){
print(root.data)
return;
}
printAll(root.left, --n)
printAll(root.right, --n)
}// considering root level is 0 height.
I guess this is the answer to find all the nodes which are at given length from root node. Is this is the question. Some one please clarify the question, it is not clear to me.
Thanks.
Small correction.
printAllNth(Tree root, int n){
if(root==null)return;
if(n==0){
print(root.data)
return;
}
printAll(root.left, n-1)
printAll(root.right, n-1)
}// considering root level is 0 height.
1. search for the node in the tree keeping track of all the nodes in the path. Use stack for storing the nodes.
2. pop first element of the stack, which is the node itself. call recursive routine to print all nodes at distance k below this node.
3. pop remaining elements, that is, each parent, keep track of the previous child(previously popped element) and get its sibling.
call above recursive routine to print elements at k-2 distance from the sibling node.
time: O(n) to find the element, O(2^k) for the 2^k+2^(k-2)+2^(k-3)+.. +1 neighbors
- mustafa khaleefuddin qureshi July 28, 2011