Amazon Interview Question
Software Engineer / DevelopersSo 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?
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
Can someone tell how the stack returned by GetParentStack looks like, in this example? Using the depth first strategy till i find the target node, first i push A
pop A, push B and C
currently C is at the top of the stack with A recently being popped out.
so, GetParentStack returns {B,C} here?
please correct me if i'm wrong.
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'
Oh this solution will work only if we have parent pointer, which is not the case. Tree is a directed graph. Sorry for confusion.
In order to successfully perform the BFS above we need some sort of graph-representation of the tree - adjacency list/matrix or even a plain array representation of the tree will do the job. We can first traverse the tree to construct one such data structure and then start the BFS from the node in question.
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.
Why to run Floyd Warshal?
Your idea is correct, make a graph of the binary tree.(un- directional graph and an edge exists between a and b in case a is parent of b or b is a parent of a.)
Now run BFS making a counter on numbers of levels travelled. when it reaches k, exit. The tree formed with BFS are the nodes with k distance from the node.
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;
}
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);
}
Can you specify the function prototype and/or example input/output? What do you mean by given nodes?
- Anonymous June 30, 2010