CareerCup

(root,7,1) will return 5
(root,7,2) will return 4

Let the parameters are root_node, target_node, K (distance)
Traverse the tree - recursive calls (inorder traversal)
If a node is the target node then print all the child nodes at distance K from target node.
While returning from a recursive call, return the distance of node from target node. If target is not yet found, return -1.
Use the distance returned to print the nodes at (k-returned_distance-2) in the other subtree via another recursive call.

Note:
If returned value to current node is X (X != -1) then target node is at distance x+1 in that subtree.
In other subtree, required nodes will be at distance (K-X-1) from current node or we can say
required nodes will be at distance (K-X-2) from root of other subtree as root of other subtree is
child of current node.

/**
 * returns distance of node from target if target has been traversed, else -1
 */
int printNodesAtDistanceKSolve(node *root, node *target, int k)
{
	if (root == NULL) {
		return -1;
	}

	if (root == target) {
		// target node is found, print all nodes at depth k in subtree rooted at target
		printNodesAtDepthKInTree(target, k);
		return 0;
	}

	int left_dist = printNodesAtDistanceKSolve(root->left, target, k);

	if (left_dist != -1) {
		// target was found in left subtree

		if (left_dist+1 == k) {
			// current node is at distance k from target node
			printf("%d\n", root->data);
		} else if (left_dist < k) {
			/*
			 * Nodes at depth (k-left_dist-2) in right subtree will be at distance k from target node,
			 * print them
			 */
			printNodesAtDepthKInTree(root->right, k-left_dist-2);
		}

		return left_dist + 1;
	}

	int right_dist = printNodesAtDistanceKSolve(root->right, target, k);

	if (right_dist != -1) {
		// target was found in right subtree

		if (right_dist+1 == k) {
			// current node is at distance k from target node
			printf("%d\n", root->data);
		} else if (right_dist < k) {
			/*
			 * Nodes at depth (k-right_dist-2) in left subtree will be at distance k from target node,
			 * print them
			 */
			printNodesAtDepthKInTree(root->left, k-right_dist-2);
		}

		return right_dist + 1;
	}

	/*
	 * target node is not found in this subtree, it will be traversed again later in other call from it's
	 * ancestor node whose subtree has target node
	 */
	return -1;
}

def getDepth(node, value) {
  if node.value == value :
    return 0;
  return 1 + max(getDepth(node.left), getDepth(node.right));
}

def getNodesOfDepth(node, depth, desired_depth) {
  if depth == desired_depth: 
    return [node.value];
  nodes = getNodesOfDepth(node.left, depth + 1, desired_depth);
  nodes.extend(getNodesOfDepth(node.right, depth + 1, desired_depth));
  return nodes
}

def F(node, value, distance) {
  depth = getDepth(node, value)
  result = getNodesOfDepth(depth - distance)
  result.extend(getNodesOfDepth(depth + distance))
  return result
}