Amazon Interview Question
SDE-2sCountry: India
Interview Type: Written Test
Why not just provide a solution outline and let others to code? Reading code is a challenge of its own.
Parent of the given node has distance 1, which is < K. I think the solution should include nodes other than the nodes below.
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.
Solution 1 sounds reasonable. Additional memory is needed.
Have problems with solution 2. What if you have such tree and looking for nodes at distance 5 of F? Looks like nothing will be found while C is the answer. Am I wrong?
A
| \
B C
|
D
|
E
|
F
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>
}
}
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);
}
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 ) ;
}
}
I think that if we were asked to print all nodes at distance k that is part of subtree of the specific node, then the above solution would be correct. But since we also have to consider the nodes which are at distance k and is not part given node's subtree, we need to modify the solution a bit.
So for its immediate parent, we need to call the same function with k-1 and its parent as k-2 and so on. And since we don't have pointer for parent we need to tweek algo.
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
- ahmad.m.bakr January 19, 2014