CareerCup

I base my answer on the fact that each node can only have one parent but multiple children.
First search upward and store each parent node in a stack. Then search downward on the parent nodes.
Second search downward and store each child also in a stack. Then search downward also on these nodes. You just have to keep track on how far you are away from the given node.

The question can be broken down into two parts as most of the above comments suggest.
1. Find the nodes which can be reached in k hops from the given node. Assuming only pointers to children are available.
2. Second part is those nodes on the upper part of the tree that are hops k away from the given node(B). The parent(A) of the given node(B), is 1 hop away. Let the given node be the left child of its parent. Hence all the nodes in the right child subtree of the parent k-1 hops away from the parent(A) are distance k - 1 + 1 = k hops away from the given node B. Similarly the grand parent of B, lets call it D, is 2 hops away. All the nodes that are k - 2 distance from D ( in the other subtree than A) are k - 2 + 2 distance away from B.


Function 1 : It returns the list of all the children which are k distance from the node s.

List<Node *>  FindNodesAtDistance(Node * s , int k)

Algo.
1. Start from root, store all nodes in a queue of maximum size k till you reach the given node. The queue will have at max k elements. The queue will eventually have a (sub)path to the given node.
2. Call FindNodesAtDistance from the given node to get all the nodes distance k in child direction.
3. Call FindNodesAtDistance on the nodes from the queue to get all the nodes distance k -i from the node. where i is the distance of the node in the queue from the given node.

def findNodesAtDistance(distance):
BFSFromCurrentNode(level = distance) (i.e. do BFS from current node but collect nodes only at level = distance)
UNION
If the pointer to the parent is available
navigate to sibling;
findNodesAtDistance(distance - 2 )

void PrintDdistance(Tree *node, int d, const int D)
{
if(node == NULL)
return;
if(d == D)
Print the node
else
{
PrintDdistance(node->left, d+1, D);
PrintDdistance(node->right, d+1, D);
}
}

I doubt we can find the distance from the parent since only the node pointer is given

FindNodes(head,node,dis)
{
Find the path of the node from the head and store in a array
DisplayNode(node,dis);
for(i=array.size();i>=0;i--)
{
temp = array[i];
dis--;
if(dis ==0) break;
DisplayNode(temp,dis);
}
}


DisplayNode(head,dis)
{
if(head == null)
{return;}
dis--;
if(dis ==0)
{Sysout(head.value); return;}
DisplayNode(head->left,dis)
DisplayNode(head->right,dis)
}

Step1: Find the path from root to given node(push all the nodes into stack from root when u are traversing to the given node).
Step2: Now from the given node call the below funct
func(Node N,distance d,Given_distance D)
{
d=D;
while(d>0 && stack.isnotempty())
{
tree *node=pop_stack()
PrintDdistance(node,d,D);
d--;
}
}
void PrintDdistance(Tree *node, int d, const int D)
{
if(node == NULL)
return;
if(d == D)
Print the node
else
{
PrintDdistance(node->left, d+1, D);
PrintDdistance(node->right, d+1, D);
}
}

/*
 * Recursive solution for getting nodes at a given distance
 */
public List<Node> getNodesAtDistance(Node rootNode, int distance) {
	List<Node> resultList = new ArrayList<Node>();
	if(rootNode==null) {
		return resultList;
	} else if(distance==0) {
		resultList.add(rootNode);
	} else {
		Node left = rootNode.getLeft();
		resultList.addAll( 
			getNodesAtDistance(left, distance-1) );
		Node right= rootNode.getRight();
		resultList.addAll(
			getNodesAtDistance(right, distance-1) );
	}
	return resultList;
}

/*
 * BFS-like implementation
 */
public List<Node> getNodesAtDistance(Node rootNode, int distance){
	List<Node> resultList = new ArrayList<Node>();
	Queue<Node> bfsQueue = new LinkedList();
	bfsQueue.add(rootNode);
	int currentLevel = 0;
	boolean hasChildNodes;
	while(!bfsQueue.isEmpty()) {
		hasChildNodes = false;
		// O(n)
		// Remove all first
		List<Node> levelNodes = new ArrayList<Node>();
		while(!bfsQueue.isEmpty()) {
			levelNodes.add(bfsQueue.remove());
		}
		// O(n)
		for (Node n : levelNodes) {
			Node leftNode = n.getLeft();
			Node rightNode = n.getRight();
			if(leftNode!=null) {
				bfsQueue.add(leftNode);
				hasChildNodes = true;
			}
			if(rightNode!=null) {
				bfsQueue.add(rightNode);
				hasChildNodes = true;
			}
		}
		// check return condition
		if(currentLevel==distance) {
			resultList.addAll(levelNodes);
			break;
		}
		// If has more childs, increment the level
		if(hasChildNodes) {
			currentLevel++;
		}
	}
	return resultList;
}

The solution can be in two phases
1. upward
2. downward

printKDistNodes(node* root, node* start, int k) {

upward(root, start, 0, k);
downward(start, k);
}

int upward(node* root, node* start, int level, int dist) {

if (root == start) { return level; }
if (root == null) { return -1; }

int right_level == upward(root->right, start, level+1, dist);
int left_level == upward(root->left, start, level+1, dist);

if (right_level != -1) {

if (right_level - level == dist) { print root; }

return right_level;

} else if (left_level != -1) {

if (left_level - level == dist) { print root; }

return left_level;
}
}

void downward(node* start, int level) {

stack cur, next;
cur.push(start);

while(!cur.isempty()) {

if (level == 0) {

print nodes in cur stack;

} else {

node* n = cur.pop();
next.push(n->left);
next.push(n->right);

if (cur.isempty()) {

level--;

while(!next.isempty()) {

node* temp = next.pop();
cur.push(temp);
}
}
}
}//while cur.isempty() loop
}// downward

Find the level of the given node. let that be L and let k be the distance
then we need to print the nodes at level L - k and L + k

1. int L = findLevel(root, start);
2. printNodes(root, L, k);

#pragma once

#include <queue>
#include <list>

struct TreeNode
{
	TreeNode(int d, TreeNode* l = NULL, TreeNode* r = NULL)
	{
		data = d;
		left = l;
		rigth = r;
	}


	int data;
	TreeNode* left;
	TreeNode* rigth;
};

struct Record
{
	TreeNode* node;
	int level;
};

void Push(std::queue<Record*>& queue, TreeNode* node, int level)
{
	if(node)
	{
		Record* record = new Record();
		record->level = level;
		record->node= node;

		queue.push(record);
	}
}


std::list<TreeNode*>* FindLevels(TreeNode* node, int level)
{
	if(node == NULL)
		return NULL;

	std::list<TreeNode*>* result = new std::list<TreeNode*>();

	std::queue<Record*> queue;

	Push(queue, node, 0);

	while(queue.empty() == false)
	{
		Record* record = queue.front();

		if(record->level == level - 1)
		{
			if(record->node->left)
				result->push_back(record->node->left);

			if(record->node->rigth)
				result->push_back(record->node->rigth);
		}
		else
		{
			Push(queue, record->node->left, record->level + 1);
			Push(queue, record->node->rigth, record->level + 1);
		}

		queue.pop();
		delete record;
	}


	return result;

}

int main(char** args, int argc)
{

	TreeNode* head = new TreeNode(1, 
		new TreeNode(2, 
			new TreeNode(4, 
				new TreeNode(6), new TreeNode(7, NULL, new TreeNode(9)))),
		
		new TreeNode(3, 
			new TreeNode(5, 
			NULL, new TreeNode(8, new TreeNode(10), new TreeNode(11))))
		);


	FindLevels(head, 4);

	return 0;
}

void find_nodes(given_node, 5, NULL)

void find_nodes(Node* node, int dist, Node* forbidden)
{
	if(node == null)
		return;
	if(dist == 0)
	{
		print(node);
		return;
	}
	
	if(node->left != forbidden)
		find_nodes(node->left, dist-1, node);
	if(node->right != forbidden)
		find_nodes(node->right, dist-1, node);		
	if(node->parent != forbidden)
		find_nodes(node->parent, dist-1, node);

}

A simple approach would be:

1.Find path from root to the given node N and store that in a stack S.
then
int d=k;
while(S is not empty)
{
struct node *temp=pop(S)
Find node t at a distnance d from temp(downward) // if t==N skip
d--;
}

I think for upward direction....we should use pre-order traversal. Once we reach the given node(return from there)...and after that everytime we call pre() we should increment the distance...print once the desired distance is reached...
For downward distance we should reach given node(make depth=0)....we can use any traversal routine...and once we reach a depth=distance each time...print the node....
Please correct me if I am wrong...

I just have a rough idea, haven't implement it yet.

findRemoteNode(int k)

define 3 kinds of recursive calls:
a. findRemoteNode( k - 1) in left_child
b. findRemoteNode( k - 1) in right_child
c. findRemoteNode( k - 1) in parent

if called by parent, only do a, b
if called by left_child, only do b, c
if called by right_child, only do a, c
if k == 0, return it self.

---------------------------------------------------

Oh...I think I am wrong, cuz the question didnot mention we have pointer to parent.

I think change the tree into the adjacency list form then use Breadth First Search can work

/* the insert code is for bst but the disk function will give correct answer for any tree */

typedef struct SearchTree {
    int val;
    struct SearchTree *l;
    struct SearchTree *r;
    struct SearchTree *p;
    struct SearchTree *s;
} bst;

void insert(bst **head, int key) {
    if (*head == NULL) {
        *head = new bst;
        (*head)->val = key;
        return;
    }
    bst *h = *head;
    while (h) {
        if (h->val < key) {
            if (h->r == NULL) {
                h->r = new bst;
                h->r->val = key;
                h->r->p = h;
                return;
            }
            h = h->r;
        }
        if (h->val > key) {
            if (h->l == NULL) {
                h->l = new bst;
                h->l->p = h;
                h->l->val = key;
                return;
            }
            h = h->l;
        }
    }
}

void disrk(bst *head, int k) {
    if (k < 0)
        return;
    if (k == 0) {
        cout << head->val << " ";
        return;
    }
    cout << head->val << " ";
    if (head->l)
        disrk(head->l, k - 1);
    if (head->r)
        disrk(head->r, k - 1);
}

void disk(bst *head, int k) {
    disrk(head, k);
    while (head->p && k > 0) {
        cout << head->p->val << " ";
        if (head->p->r == head) {
            disk(head->p->l, k - 2);
        }
        if (head->p->l == head) {
            disk(head->p->r, k - 2);
        }
        k = k - 1;
        head = head->p;
    }
}

Won't BFS do the job?

Don't get fooled by the "Binary Tree" notion. Treat it as a graph and use BFS to find all nodes that are k hops away from it

Idea would be to recognize the branch on which the given element lies. Use a simple pre-order traversal to store elements in stack (maximum size: depth of a tree).
Once we have the corresponding branch including the given element one can print the elements at a distance (k-(distance of current node and given node)). Below code gives and idea.

PS: this code is not tested and intent is to give an idea:

//this method is to populate stack with required branch elements
bool func(struct tNode *ptr,int *stack,struct tNode *res)
{
     if(ptr==NULL)
     return False;
     if(ptr==res||func(ptr->left,stack,res)||func(ptr->right,stack,res))
     {
         push(stack,ptr);                                                               
         return True;
     }
     return False;
}

//This method is to print elements at k distance from a particular node
void printElem(struct tNode *ptr,struct tNode *par,int d,int k)
{
     if(ptr==NULL||ptr==par)
     return;
     if(d+1==k)
     {
               printf("\n%d",ptr->num);
               return;
     }
     printElem(ptr->left,par,d+1,k);
     printElem(ptr->right,par,d+1,k);
}

int main()
{
    struct tNode *stack[<depth of tree>],*temp,*prev;
    int d,k;
    func(root,stack,res);
    temp=NULL;
    d=5;
    k=0;
    while(!isEmpty(stack)&&k<=n)
    {
          prev=pop(stack);
          printElem(p,temp,0,d-k);
          k++;
    }
}

Nodes we are interested in are: kth level grand parent and kth level grand children
To find kth level grand parent:
1. Get BFS trace till you encounter N in the tree.
2. In this trace array, parent node's index=floor(a node's index/2). Use this to go up k levels terminating if you hit zero before kth grand parent.
To find kth level grand children: BFS or DFS till level k

struct Node
{
	Node *left;
	Node *right;
	int distance; //initialized to -1 at the beginning, means the distance is not calculated yet.
}

void CalcDistance(Node *current, Node *node)
{
	//pre-order
	if (!current) return;
	if (current == node) node->distance == 0;
	if (!current->left)
	{
		CalDistance(current->left, node);
		if (current->left->distance !=-1) current->distance == current->left->distance + 1;
	}
	if (!current->right && current->distance == -1)
	{
		CalDistance(current->right, node);
		if (current->right->distance !=-1) current->distance == current->right->distance + 1;
	}		
}

void ReCalcDistance(Node *current, int distance)
{
	//pre-order
	if (!current) return;
	if (current->distance == -1) current->distance == distance;
	ReCalDistance(current->left, current->distance+1);
	ReCalDistance(current->right, current->distance+1);
}

void Print(Node *current)
{
	if (!current) return;
	if (current->distance == k) print current;
	Print(current->left);
	Print(current->right);
}

int _tmain(int argc, _TCHAR* argv[])
{
        //initialize the tree...

	CalcDistance(root, node);
	ReCalcDistance(root, root->distance);
	Print(root);
	return 0;
}

import java.util.Stack;
	class BinTree
		{
			int data;
			BinTree left;
			BinTree right;
			int level;
		}

		public class PrintDistanceKByNonRecur {
			/**
			 * @param args
			 */
			public static void main(String[] args) {
				// TODO Auto-generated method stub
				BinTree node=null;
					node=buildBinTree(node);
					bfs(node,4);
			}

				
			public static BinTree buildBinTree(BinTree node)
			{
				BinTree top=null;
				if(node==null)
				{
					node=new BinTree();
					node.data=100;
					node.level=0;
					System.out.println("data "+100+" added to root node");
					top=node;
				}

				int[] a={56,34,14,26,38,48,57,64,71,70};
				
				for (int i:a)
				{	
					node=top;
					//int random=(int) (Math.random()*100);
					//System.out.println("Item is "+i);
					AddNode(node,i,0 );
				}
				
				System.out.println("Tree is built.....");
				return top;
			}
			
			public static void bfs(BinTree node,int distance)
			{

				if(node==null )
				{
					
					return;
				}
				

				if(node.level==distance)
				System.out.println(node.data);
				//distance--;
				bfs(node.left,distance);
				bfs(node.right,distance);
				
				
			}
			
			
			public static void AddNode(BinTree node,Integer data,int level)
			{
				level++;
				if(data<node.data)
				{
					if (node.left != null)
					{
						AddNode(node.left,data,level);
					}	
					else
					{
						BinTree temp=new BinTree();
						temp.data=data;
						temp.level=level;
						node.left=temp;

						System.out.println("data "+data+" added to left node");
					}
				}
				else if(data>node.data)
				{ 
					if (node.right != null)
					{
						AddNode(node.right,data,level);
					}	
					else
					{
						
						BinTree temp=new BinTree();
						temp.data=data;
						temp.level=level;
						node.right=temp;
						System.out.println("data "+data+" added to right node");
					}	
				}else {System.out.println("Duplicate entry "+data);return;}
			}
			
		}