CareerCup

This can be done by BFS algorithm and you only consider nodes that at distance K from the given node. The given node is the parent of the tree we need to parse. A java code for this problem can be like that

public ArrayList<Node> printNodes(Node node, int k){
		Queue<Node> queue = new LinkedList<>();
		ArrayList<Node> list = new ArrayList<>();
		int level = 0;
		int nodesToProcess = 1;
		int nodesInNextLevel =0;
		queue.add(node);
		while(!queue.isEmpty()){
			Node n = queue.remove();
			nodesToProcess--;
			if(n.left!=null){
				queue.add(n.left);
				nodesInNextLevel++;
			}
			if(n.right!=null){
				queue.add(n.right);
				nodesInNextLevel++;
			}

			if(level == k) list.add(n);

			if(nodesToProcess==0){
				level++;
				nodesToProcess = nodesInNextLevel;
				nodesInNextLevel=0;
				if(level>k) break;
			}
		}
		return list;
	}

I can think of 2 solutions for it

1) Run DFS on the tree to find parent of each node. Now this tree becomes a graph. Run BFS/DFS to find all nodes at distance K

2) Use the concept of rotating trees as in red black trees.
First take the tree with root at the starting node (arbitrary node) and find all nodes at level K. These are all the nodes at distance K in the sub tree.
Then remove all child nodes from the starting node and do multiple rotations so that this node becomes the root. Now find all nodes at level K
The union of both of these is the solution.

I was thinking along similar lines as Arrantinsane. I split the problem into two parts:
+ From the binary tree root, see if the target node can be found at specified distance/depth.
+ From the target node, find all nodes at specified distance/depth.
Here is my pseudo code.

void
find_node_at_distance(root, tgt, distance)
{
    lroot = root;                       // local copy of root.
    ldistance = distance;
    while (lroot) {
        if (tgt) {
            if (lroot->data == tgt->data) {
                break;
            }
        }
        if (ldistance < 0) {
              break;
        }
        ldistance--;

        if (tgt->data < lroot->data) {
            lroot = lroot->left;
        } else {
            lroot = lroot->right;
       }
  } 

  if (ldistance == 0) {
      printf("root is at distance of %d from tgt\n", root, distance);
  }
}

main()
    find_node_at_distance(root, tgt, 2);          // ex distance of 2.
    find_node_at_distance(tgt->left, NULL, 2-1);  // NULL means any node at given dist.
    find_node_at_distance(tgt->right, NULL, 2-1);

This problem can be divided into two parts:

1) All nodes K distance away from arbitrary node in arbitrary node's subtree.
2) All nodes K distance away from arbitrary node above to this arbitrary node.

First part is quite easy.

void kdistanceNodes (tree *root, int K)
{
	if (root)
	{
		if (K == 0)
		{
			print << root->key;
		}
		kdistanceNodes (root->left, K-1);
		kdistanceNodes (root->right, K-1);
	}
}

when arbitrary node is found
1) process all K distance node in its subtree
for second part,
2) if arbitrary node is not found, at every node, keep distance from leaf node in left subtree and from leaf node in right subtree
3) if arbitrary node is found, at every node, keep distance from arbitrary node from either of subtree and then search for remaining other subtree (K - distance from arbitrary node)

pair<bool, int> printKNodes (tree *root, int depth, int node, int K)
{
	if (!root) return make_pair(false, 0);
	if (K < 0) return make_pair(false, 0);

	/*If Node found, then print all nodes at K distance in subtree*/
	if (node == root->key)
	{
		if (K == 0) {print node, return <true, 1>}
		kdistanceNodes (root->left, K-1)
		kdistanceNodes (root->right, K-1)
		return <true, 1>
	}
	else
	{
		pair<bool, int> left = printKNodes (root->left, depth+1, node, K)
		/*If node is found in left subtree and current node is still <=K nodes away from arbitrary node */
		if (left.first == true && left.second <= K)
		{
			if (K - left.second == 0)
			{
				print root->key
			}
			else if ( (K - left.second) > 0)
			{
				/*remaining distance from arbitrary node to right subtree via this root*/
				kdistanceNodes (root->right, (K - left.second - 1) )
			}
			return <true, left.second+1> //pair
		}
		pair<bool, int> right = printKNodes (root->right, depth+1, node, K)
		/*If node is found in right subtree and current node is still <=K nodes away from arbitrary node */
		if (right.first == true && right.second <= K)
		{
			if (K - right.second == 0)
			{
				print root->key
			}
			else if ( (K - right.second) > 0)
			{
				/*remaining distance from arbitrary node to left subtree via this root*/
				kdistanceNodes (root->left, (K - right.second - 1) )
			}
			return <true, right.second+1> //pair
		}
		/*If arbitrary node has not been found return total depth from leaf node*/
		int biggerSubtree = (left.second > right.second) ? left.second : right.second;
		return <false, biggerSubtree+1>
	}
}

void printAtLevel(Node *treenode, int level)
{
	if(treenode==NULL)
		return;
	if(level==1)
	{
		printf(" %d ",treenode->data);
	}
	else if(level > 0)
	{
		printAtLevel(treenode->right, level-1);
		printAtLevel(treenode->left, level-1);
	}
}

public static int distance;
public static ArrayList<Node> result;

public void findKth(Node root, Node target){
findKth(root, -1, target);
}

private int findKth (Node n, int k, Node target ){
if( n == null ){
return k;
}
if(n == target){
k= distance;
}
if(k == 0){
result.add(n);
return k++;
}
if(k == -1){
int temp 1 = findKth( n.left , k, target);
int temp2 = findKth (n.right , k , target);
}else{
int temp 1 = findKth( n.left , --k, target);
int temp2 = findKth (n.right , --k , target);
}
if((temp1-distance)==distance || (temp2-distance) == distance ){
result.add(n);
}
return temp1== -1? temp2++ : temp1++;
}

O(n) complexity, any opinion?

we have to print all nodes which are child of desired nodes and are child of parent nodes.

public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance)
        {
            if ((root == null) || (iDistance < 0))
                return -1;
               
            int lPath = -1, rPath = -1;

            if(root.value == requiredNode)
            {
                PrintChildNodes(root, iDistance);
                return iDistance - 1;
            }

            lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance);
            rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance);

            if (lPath > 0)
            {
                PrintChildNodes(root.right, lPath - 1);
                return lPath - 1;
            }
            else if(lPath == 0)
            {
                Debug.WriteLine(root.value);
            }

            if(rPath > 0)
            {
                PrintChildNodes(root.left, rPath - 1);
                return rPath - 1;
            }
            else if (rPath == 0)
            {
                Debug.WriteLine(root.value);
            }

            return -1;
        }

        public void PrintChildNodes(Node aNode, int iDistance)
        {
            if (aNode == null)
                return;

            if(iDistance == 0)
            {
                Debug.WriteLine(aNode.value);
            }

            PrintChildNodes(aNode.left, iDistance - 1);
            PrintChildNodes(aNode.right, iDistance - 1);
        }

(assuming binary search tree)
search for the node, recording parents in path to it
for parent of the node, find all children k-1 from there
for grandparent of the node, find all children k-2 from there
etc.

finally find children of that node that are distance k

void printKDistant(node *root , int k)    
{
   if(root == NULL) 
      return;
   if( k == 0 )
   {
      printf( "%d ", root->data );
      return ;
   }
   else
   {      
      printKDistant( root->left, k-1 ) ;
      printKDistant( root->right, k-1 ) ;
   }
}