CareerCup

Can you specify the function prototype and/or example input/output? What do you mean by given nodes?

So this question is to find the number of nodes between root and a passed in node? Why do you say distance can be upwards or downwards? What does that mean? I would think root is at the top and you then traverse down to the other node, counting nodes you visit. Recursive depth first is easiest in this case, counting nodes. Am I way off guys?

represent the tree using arrays. if the parent is at Ith node, the left children will be at 2i and the right one will be at 2i + 1,
Using this representation you can traverse in both the directions without having parent pointers.

any comments ?

Okay, we're given a binary tree (presumed unbalanced and unsorted), a root node, a target node and a distance k.

The strategy is 3 part.
1. Walk the tree using a stack pushing and popping until you find the target node. This leaves you with a stack containing the parents of the target node. Include the target node at the top of your stack.
2. Create a function GetNodes(Node current, int distance) that adds the appropriate nodes to a list. You'll use it in step 3 to call the left and right children recursively.
3. Figure out which nodes to pump through your function GetNodes. You want to send the target node, and the "other child" of the parent node only. Thing is, you don't know whether you're the right or the left, so you have to keep a temp variable on hand to compare the children. To do this, you need to start with the following initial values:
k = distance;
childNode = targetNode;
In a while loop that exits when the stack is empty or k = 0, you do the following:
a. if curnode.left is not the childNode, then GetNodes(curnode.left, k-1)
b. repeat for right child.
c. decrement k
d. pop the stack to get new curnode. Repeat.

Here's code for steps 2 and 3, and a stub for step 1. Note that this implementation assumes that the tree implementation is abstracted and that each node only contains a left and a right but no parent. If a node is parent-aware, the same strategy applies but step 1 is faster and easier to implement.

This implementation is O(n)

C#:

public class NodeGetter
{
    private List<Node> nodes = new List<Node>();

    public List<Node> GetNodes(Node root, Node target, int distance)
    {
         Stack myStack = GetParentStack(root, target);
         int k = distance;
         Node child = target;
         
         while (!myStack.isEmpty && k >= 0)
         {
             Node curNode = myStack.Pop();
             if (k == 0)
             {
                 nodes.Add(curNode);
                 break;
             }
             if (curNode.Left != child)
             {
                 FindNodes(curNode.Left, k-1);
             }
             if (curNode.Right != child)
             {
                 FindNodes(curNode.Right, k-1);
             }
             k--;
             child = curNode;
         }
    }

    private void FindNodes(Node cur, int distance)
    {
       if (cur == null) return;
       if (distance == 0)
       {
           nodes.Add(cur);
       }
       else
       {
           FindNodes(cur.Left, distance-1);
           FindNodes(cur.Right, distance-1);
       }
    }

    private Stack GetParentStack(Node root, Node target)
    {
         // Walk tree using depth-first strategy pushing and popping til find target.
         return myStack; 
    }

My assumption of what the question states regarding going 'up or down' is represented in this example.

Say target node is C and distance 3.
That should return the set { T, D, E }

A
            B                       C
       D         E              F          G
   H      I    J    K         L    M    N      O
P           S               T
   Q

explain a little more pls....

explain a little more pls....

Wont BFS solve the problem simply. BFS layers the tree interms of the distance from the root node. Given any node and given that we have already performed BFS, we know the level of the node from root say m. Getting the nodes of distance k (up or down) is just the matter of knowing nodes at the levels that are m-k and m+k. Am I Missing something here?

BFS can be used to find the distance between two nodes in a graph (or tree). Start BFS tree from node from which you have to find all nodes with distance 4.

In BFS as soon as you enqueue a child node 'N' of node 'R' at that point check distance array if((d[N] = d[R] + 1) == 4) output node 'N'

If we represent binary tree in the form of array. (2i - left node and 2i+1 - right)
1. From the given node (n) - (proceeding through 2n and 2n+1, find all child nodes which are at a distance k)
2. go to n/2, find all child nodes, which are at a distance k-1
3. go to n/4, find all child nodes which are at a distance k-2
proceed till n/2powx reaches root node.

How about thinking the problem this way?

A binary tree is actually a graph right? Usually when we think about BT, the edge is unidirectional (parent->child). But in this case, apparent, travelling up is also okay. Say the node is A, it has two children B, C. If k = 1, then B and C should be also included as well.

So how about doing this

1. construct the tree as a graph with node as vertex and child links as bidirectional edges.

2. use Floyd Warshall algorithm to find out all the distance between any two nodes.

3. now all we need to do is to scan the distance matrix for the row and column correspnoding the target node A, and try to find all the other nodes B, where dist[a][b] or dist[b][a] == k.

Only slight addition to "Someguy" code and done in C++

void getNodes (Node *root, Node *target, int distance, Node **addNodes)
{
    if (root == NULL || target == NULL || distance < 0)
        return
    Queue q;
    bool isPresent = getparentQueue (Node *root, Node *target, Queue &q);
    if (!isPresent)
        return;
    Node *child;
    while (!q.isEmpty() && distance >= 0)
    {
        Node *current = q.deQueue ();
        if (distance == 0)
        {
            addNodes.add (current);
            break;
        }
        if (current->left != child)
            findNodes (current->left, distance - 1,addNodes);
        if (current->right != child)
            findNodes (current->right, distance - 1, addNodes);
        distance--;
        child = current;
    }
}

void findNodes (Node *root, int distance, Node **addNodes);
{
    if (root == NULL)
        return;
    if (distance == 0)
    {
        addNodes.add (root);
    }
    else
    {
        findNodes (root->left, distance - 1, addNodes);
        findNodes (root->right, distance -1, addNodes);
    }
}

bool getParentQueue (Node *root, Node *target, Queue &q)
{
    if (root == NULL)
        return false;
    bool leftNode = getParentQueue (root->left, target, q);
    bool rightNode = getParentQueue (root->right, target, q);
    if (root == target)
    {
        q.enqueue (root);
        return true;
    }
    if (leftNode)
    {
        q.enqueue (root);
        return true;
    }
    else if (rightNode)
    {
        q.enqueue (root)
        return true;
    }
    else
        return false;
}

NA

My solution :
Traversal until find the node, search down first , then return back to root, at every node on the way back, check if the other subtree have some nodes with right distance

// find node which have distance k to root
void	FindDistanceK(NodePosition root, int k )
{
	if (root == NULL || k < 0)
		return ;

	if(k == 0)
	{
		cout << root->Element << endl;
		return;
	}

	FindDistanceK(root->Left, k-1);
	FindDistanceK(root->Right, k-1);
}

/*work function: traversal first until find node, search down ,  then return back to root, at every node *on the back path, check if the other subtree have some nodes with right distance
*/
void	DoFindK(NodePosition root, NodePosition node, int k, bool &find, int &updistance)
{
	if(root == NULL)
		return ;

	// find node
	if (root == node )
	{
		find = true;
		FindDistanceK(root, k); // find any node below it
		return;
	}

	// go left
	DoFindK(root->Left, node, k, find, updistance);
	if ( find)
	{
		updistance++;
		if(updistance == k)
			cout << root->Element << endl;
		else
			FindDistanceK(root->Right, k-updistance-1);
		return;
	}

	// go right
	DoFindK(root->Right, node, k, find, updistance);
	if ( find)
	{
		updistance++;
		if(updistance == k)
			cout << root->Element << endl;
		else
			FindDistanceK(root->Left, k-updistance-1);
		return;
	}
}
// wrapper function
void	FindK(NodePosition root, NodePosition node, int k)
{
	bool find = false; // checker to indicate if node is found
	int  updistance = 0;
	DoFindK(root, node, k, find, updistance);
}