In a binary tree, given a root and a number K. You have to find the all nodes at distance K from given root node.
For example in a given tree, if K =2 then Output should be 4,5,6
if k = 1 then Output should be 2,3
// structure of tree struct node { int value; struct node* left; struct node* right; }; // function to print nodes at k distance void kDistanceNodes(Node *root , int k) { if(root == NULL || k < 0) return; if( k == 0 ) printf("%d", root->value ); else { kDistanceNodes(root->left, k-1 ) ; kDistanceNodes(root->right, k-1 ) ; } }
Time complexity: O(N) as we have to traverse the compelete tree, N is the number of nodes in a tree
Hi
I love your recursive solutions
Just though to give iterative manner a try. I was thinking initially it should be very easy, but struggled to get working correctly. My java method code snippet is following.
public static void nodeAtKDistance(Node root, int distance){ //assume dist is not more than tree height
Queue treeQueue1 = new LinkedList();
Queue treeQueue2 = new LinkedList();
if(distance == 1){
System.out.println(root.getData());
}
else{
treeQueue1.add(root);
for(int i=1; i<distance; i++){
if( (i & 1) != 0){ // for i==odd
while(!treeQueue1.isEmpty()){
System.out.println("Hello");
Node current = treeQueue1.poll();
if(current.left != null){treeQueue2.add(current.left);}
if(current.right != null){treeQueue2.add(current.right);}
}
}
else{ //for i==even
while(!treeQueue2.isEmpty()){
System.out.println("Hi");
Node current = treeQueue2.poll();
if(current.left != null){treeQueue1.add(current.left);}
if(current.right != null){treeQueue1.add(current.right);}
}
}
}
}
if( (distance & 1) == 0 ){ //distance value is even, pop all the values from TreeQueue1
while(!treeQueue2.isEmpty()){
Node temp = treeQueue2.poll();
System.out.print(temp.getData() + " ");
}
}
else{
while(!treeQueue1.isEmpty()){
Node temp = treeQueue1.poll();
System.out.print(temp.getData() + " ");
}
}
}
void printNodesAtDistanceK(node *root,int level,int k) {
if (!root)
return;
else if (level == k) {
cout<val<left,level + 1,k);
printNodesAtDistanceK(root->right,level + 1,k);
}
}