Print nodes at K distance from root in binary tree

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

Binary Tree

// 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

One Thought on “Print nodes at K distance from root in binary tree

  1. Rajiur Rahman on September 16, 2015 at 10:43 am said:

    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() + " ");
    }
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation