Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
BFS to know the depth of all nodes in the tree and then consider those which comprise u + d = K. u = upward distance, d = downward distance from the start node. Ex:- K= 4, and start node is at depth 3.
The u and d can take values (0,4)(1,3)(2,2)(3,1)(4,0). Meaning consider the upward distance of 0 and downward distance of 4 from from start node => 3 + 4 = 7. Consider nodes beneith start node which are at level 3. Similarly for other combinations.
As and when fetching the nodes do an insertion sort.
CORRECTION at the end of 1st para: Consider nodes beneith start node which are at level 7. Similarly for other combinations.
void PrintKDepth(node *root, int depth)
{
if (root == null) return;
if (depth == 0 )
{
Print the root;
}
PrintKDepth(root->left,depth-1);
PrintKDepth(root->right,depth-1);
}
int PrintAllKthDistance(node *root, node *start, int depth K)
{
if(root == null) return -1;
if(root == start)
{
PrintKDepth(root->left, k);
PrintKDepth(root->right, k);
return k-1;
}
int leftDepth = PrintAllKthDistance(root->left,start,found,K);
if(leftDepth == 0)
{
print the node;
}
else if (leftDepth > 0)
{
PrintKDepth(root->right, leftDepth);
return leftDepth-1;
}
int rightDepth = PrintAllKthDistance(root->right, start, found, k);
if(rightDepth == k)
{
print the node
}
else if (rightDepth > 0)
{
PrintKDepth(root->left, rightDetph);
return rightDepth-1;
}
return -1;
}
This code handles the up distance from start ..
on recursion - when we return to up from start node, and if its value is greater than 0, then we are querying left/right subtree depending on the start node. This way we query up node and also other side of subtree..
Please give an example..the case ..where you are not able to print out all the nodes from the start node...
Do we need to print only the nodes which are connected to start node and are at K distance from start node OR We should print all the nodes from the Kth distance level?
As par my understanding, We have to print K distance from the start node assuming as graph.
so if we have to only print the Kth distance of path node, then you simply put a very easily contraint...that would also be solvable by this methog
Is there any constraint on the space usage? if not, lets say that we're allowed to use extra space of O(n). We can create an array, do a BFS on the binary tree and store the nodes encountered in our array. One we're done with the BFS, we can find the nodes with satisfy the distance property. For example, lets say our tree was:
4
/ \
2 6
/ \ / \
1 3 5 7
Now if we did a BFS, we would get the array as: 4,2,6,1,3,5,7. Lets say the start node is root node (i.e. 4), the node to be searched is 3 and K = 2.
Now we know that we can find the children of a node at 2n+1, 2n+2 position (en.wikipedia.org/wiki/Binary_tree#Arrays)
Given this array, we can look for the index of node 3 (which happens to be 4 in our example). Now, we are looking for all nodes which are at a distance of k = 2 from node 3. We know that the parent of 3 (if it exists) must be at a distance = 1 from 3. This parent can be found at (index of node3 -1)/2. This node is at index = 1. Now node 3 can ask its parent to return all nodes which are at a distance (k-1) [such that k-1 ==0].Node 2 sees that there are only 2 nodes which satisfy this property: Node 4 and Node 1 (ignoring Node 3 itself). so these 2 nodes are printed. Node 3 also asks its children to return all nodes which are at a distance of k.
Hence, recursively it looks possible to discover all the nodes (including siblings) which are at a distance of k from node 3.
This is just an initial idea. And requires O(n) extra space. Runs in O(n) time.
Start from root node. Identify if start node is to left of root node or right of root node.
Start bfs:
label each node with the 'level' value
also label each node with flag '1', if nodes are on other side of 'start' node
if nodes have startnode as ancestor , label them as '2'
else label them with '0'.
Now, while printing, do in-order traversal, and only print nodes that meet the following condition:
if ( node.side = '1' and startnode.level + node.level == k ) print node
if ( node.side = '2' and node.level - startnode.leve == k ) print node
if ( node.slide = '0' )
common ancestor between startnode and node is at l = abs(startnode.level - node.level)
now if l + node.level == k , then print.
Use recursion to first find downwards distance
Signature is:
kDistDown(node *root, node *start, int k) {
<check for halting condition: k=0 and start !=null >
kDistDown(node *root, node *start->left, k-1)
kDistDown(node *root, node *start->right, k-1)
}
Now to check the upwards condition.
This is kind of a hack really. By no means elegant.
Write a recursive function to exhaustively search a tree for a given node returning the distance from the ROOT as the output.
Call the function TWICE passing root->left and root->right as args.
Now you'll know which subtree our start node is on. Left or right.
Also you'll know the distance from root to the start node.
Let this be 'n'.
Exhaustively search for all nodes at a distance k-n in the OPPOSITE subtree.
The Algorithm would be something like this(would post the code later)
1.Do a DFS traversal for the tree(Inorder)
2.In the Process node part call a sub routine find_distance between_two_nodes
3.Check if the return val of 2 is equal to k, if yes print it or store it in an array(for sorting)
find_distance between_two_nodes works as follows
1. Find LCA of the 2 nodes under discussion
2.from the LCA call get_node_distance_from_lca subroutine for both the nodes and add the result and return
get_node_distance_from_lca works as follows
find the difference between the level of lca and the node(using BFS)
Space Complexity : S(n)--queue
Time Complexity : O(n)
I think your solution in O(n^2). Since, you do the processing for each pair of nodes. And, then between each pair of nodes you do an bfs. which in O(n)
No,I am calculating distance of the given node with all other nodes(for LCA) and the other for length of path, the maximum nodes that would be traversed is again n, so the total complexity is O(n) + O(n) =~ O(n).
sorry,you are right,it will trend towards O(n2) and one optimization could be done, i.e. when doing a level order traversal store the nodes in a map(hash on node value as key) and store its level as the value.Now during the calculation of the path length from lca to each node, the lookup should only be O(1).
I think you can do it without recursion (assuming bst, otherwise sorted order does not make sense):
Find your node using binary search and note the path like LLR
start a stack based in order traversal and check whether the distance is less than or equal to K
The distance calculation: find the longest prefix of the two paths then add the tail length of both paths. So, distance between LLR and LR is 3 (L is common, dist: len(LR) + len(R) = 2+1)
Don't enter a subtree/ignore pop from the stack if already too far from the original node (limiting the number of visited nodes to K)
To speed up the distance calc a little bit, you can supply the parent result and add the child difference only.
Time complexity: O(logn) + O(k)
5
/ \
2 8
/ \ / \
-4 4 6 9
input :
Root node: 5
search node: 8
Distance (K): 1
output : 5, 6, 9
if k is 3 then output should be -4 and 4 respectively, the problem i feel is how to navigate upwards considering that we do not have reference to parent node.
2 Passes
1st Pass
1. Find the level at which startNode occurs using recursion to traverse the tree
2nd Pass
1. Print all nodes at level- distance and level+distance using recursion to traverse nodes
Code follows in Java
private static int findLevel(TreeEntry root,TreeEntry startNode,int level) {
int level1,level2;
if (root == null)
return -1;
else {
if (root == startNode)
return level;
level1 = findLevel(root.left,startNode,level+1);
level2 = findLevel(root.right,startNode,level+1);
}
if (level1 != -1)
return level1;
if (level2 != -1)
return level2;
return -1;
}
private static void printNodes(TreeEntry root,int interestedLevel1,int currLevel,int interestedLevel2) {
if (root == null)
return;
else {
if ( (currLevel == interestedLevel1) || (currLevel == interestedLevel2) ){
System.out.println(root.data);
}
printNodes(root.left,interestedLevel1,currLevel+1,interestedLevel2);
printNodes(root.right,interestedLevel1,currLevel+1,interestedLevel2);
}
}
// Takes searchNode (startNode) as int and prints all the nodes // at distance k from it. But the printed nodes are not in sorted //order
void printKDistanceNodes( BinaryNode *root , int searchNode ,int level , int x , int *y , int *found )
{
if( root == NULL ) return ;
if( root->data == searchNode )
*found = 1;
if( *found == 1 )
{
printKDistanceNodes ( root->left , searchNode , level, x+1, y , found);
printKDistanceNodes ( root->right , searchNode , level, x+1, y , found);
}
else
{
printKDistanceNodes ( root->left , searchNode , level, x, y , found);
if(*found)
printKDistanceNodes ( root->right , searchNode , level, x+1, y , found);
else
printKDistanceNodes ( root->right , searchNode , level, x, y , found);
if(found)
printKDistanceNodes ( root->left , searchNode , level, x + 1, y , found);
}
if( x + *y == level )
{
cout<< root->data << "\n";
}
if(*found && x == 0 )
(*y)++;
return;
}
void printk(Node root, int k)
{
if(root!=NULL )
{
if(k==0) cout<<"@"<<root->data<<"@"<<endl;
else{printk(root->left, k-1);
printk(root->right, k-1);}
}
}
^ above to print downword .. upward can be similarly printed by calculating the depth of the given node.. then calculating relative distance of the level to be printed from node.. then by calling the above function again
I hope following looks cleaner.
public void printKDistanceNodes(TNode head, TNode node, int k){
if(null == head || null == node || k < 0){
return;
}
if(head.equals(node)){
printNodesInDistanceKFromRoot(head, k);
} else {
initializeAndUpdateDitanceFromRootToNode(head, node);
printNodesInDistanceKFromAGivenNode(head, node, k);
}
}
/* This function initializes the distances of the nodes from root
* to the given node in using post order traversal
Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(4))
1
2 3
4 6
Transforms to
1,-2
2,-1 3
4,0 6
In the above minus negative sign denotes whether node in in left side or right side.
Negative value means node is in the left side.
Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(6))
1
2 3
4 6
Transforms to
1,2
2 3,-1
4 6,0
*/
public ReturnStrcture initializeAndUpdateDitanceFromRootToNode(TNode head, TNode node){
ReturnStrcture c = new ReturnStrcture();
ReturnStrcture l = new ReturnStrcture();
ReturnStrcture r = new ReturnStrcture();
int distance = 0;
if(head.equals(node)){
c.setDistance(0);
c.setIsFoundNode(true);
head.setDistance(distance);
return c;
}
l = initializeAndUpdateDitanceFromRootToNode(head.getLeft(), node);
r = initializeAndUpdateDitanceFromRootToNode(head.getRight(), node);
if(l.getIsFoundNode()){
c.setDistance(l.getDistance() + 1);
c.setIsFoundNode(true);
distance = -(l.getDistance() + 1);
} else if (r.getIsFoundNode()) {
c.setDistance(r.getDistance() + 1);
c.setIsFoundNode(true);
distance = r.getDistance() + 1;
} else {
c.setIsFoundNode(false);
}
head.setDistance(distance);
return c;
}
/*
* This function uses another function printNodesInDistanceKFromRoot and print all the nodes
* that are in distnce k from given node.
*/
public void printNodesInDistanceKFromAGivenNode(TNode head, TNode node, int k){
if(head.equals(node)){
printNodesInDistanceKFromRoot(head, k);
return;
}
if(head.getDistance() < 0){
// Given node is in the left subtree
if(Math.abs(head.getDistance()) == k){
System.out.println("Node value - "+head.getVal());
} else if (Math.abs(head.getDistance()) < k){
printNodesInDistanceKFromRoot(head.getRight(), k-1-(Math.abs(head.getDistance())));
}
printNodesInDistanceKFromAGivenNode(head.getLeft(), node, k);
} else if (head.getDistance() > 0){
// Given node is in the right subtree
if(head.getDistance() == k){
System.out.println("Node value - "+head.getVal());
} else if (head.getDistance() < k){
printNodesInDistanceKFromRoot(head.getLeft(), k-1-head.getDistance());
}
printNodesInDistanceKFromAGivenNode(head.getRight(), node, k);
}
}
/*
* Print all the values nodes with distnce k from the head.
*/
private void printNodesInDistanceKFromRoot(TNode head, int k) {
if(head != null){
if(k == 0){
System.out.println("Node value - "+head.getVal());
return;
} else {
printNodesInDistanceKFromRoot(head.getLeft(), k-1);
printNodesInDistanceKFromRoot(head.getRight(), k-1);
}
}
}
public class TNode {
Integer val;
TNode left;
TNode right;
Integer distance;
public Integer getVal() {
return val;
}
public void setVal(Integer val) {
this.val = val;
}
public TNode getLeft() {
return left;
}
public void setLeft(TNode left) {
this.left = left;
}
public TNode getRight() {
return right;
}
public void setRight(TNode right) {
this.right = right;
}
public Integer getDistance() {
return distance;
}
public void setDistance(Integer distance) {
this.distance = distance;
}
}
public class ReturnStrcture {
private int distance;
private boolean isFoundNode; // 1 for left, 2 for right
public int getDistance() {
return distance;
}
public void setDistance(int distance) {
this.distance = distance;
}
public boolean getIsFoundNode() {
return isFoundNode;
}
public void setIsFoundNode(boolean isFoundNode) {
this.isFoundNode = isFoundNode;
}
}
steps:
1. get the distance of the start node in the tree.
2. make a function printk(node , distance) which prints all the nodes at a level of k from the given node passed as a paramenter.
3. Run the printk(start node , k) with start node and k , it prints the nodes at level k down from the start node.
4. let k=4 for eg. and the level of start is 6 , so 6-4 = 2 is the level upto which we need to print the nodes. these will be the node k distance from the start node
5. done
fun(node* root,node*start,int k)
{
static int flag=0,level= 0;
if(n!=NULL)
{
if(root==start) // start node found now proceed
{ flag=1;
}
if( flag==1)
{
level++;
if(level==k)
cout<<root.data;
return;
}
fun(n->left);
if(level==k&&n!=start)
{ return;
}
else if(n==start)
{
level=0;
}
fun(n->rite)
if(n==start)
{ k=1;
}
}
}
Going down was easy but once i hit the K nodes from bottom, i start returning the value 2*k-1 up along the path.This way , when we again hit the target node while backtracking, we are at (2k-1)/2 and as we move up, we will again be at 0 (or -k) value
private static int fn(Node root, Node x, int level, int curr) {
if (root == null) return -1;
if (curr == level) {
System.out.println(root.data);
return (2 * (level)) - 1;
}
if (root == x || curr > 0) {
curr++;
}
int l = fn(root.left, x, level, curr);
int r = fn(root.right, x, level, curr);
if ((max(l, r) != -1)&&( max(l,r)==0)) {
System.out.println(root.data);
return -1;
} else{
return max(l,r)-1;
}
Here is O(n) solution, but program modifies the tree node, it stores the distance from root to current node.
public void printKDistanceNodes(TNode head, TNode node, int k){
if(null == head || null == node || k < 0){
return;
}
if(head.equals(node)){
printNodesInDistanceKFromRoot(head, k);
} else {
initializeAndUpdateDitanceFromRootToNode(head, node);
printNodesInDistanceKFromAGivenNode(head, node, k);
}
}
/* This function initializes the distances of the nodes from root
* to the given node in using post order traversal
Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(4))
1
2 3
4 6
Transforms to
1,-2
2,-1 3
4,0 6
In the above minus negative sign denotes whether node in in left side or right side.
Negative value means node is in the left side.
Tree after the execution of initializeAndUpdateDitanceFromRootToNode(head, nodeof(6))
1
2 3
4 6
Transforms to
1,2
2 3,-1
4 6,0
*/
public ReturnStrcture initializeAndUpdateDitanceFromRootToNode(TNode head, TNode node){
ReturnStrcture c = new ReturnStrcture();
ReturnStrcture l = new ReturnStrcture();
ReturnStrcture r = new ReturnStrcture();
int distance = 0;
if(head.equals(node)){
c.setDistance(0);
c.setIsFoundNode(true);
head.setDistance(distance);
return c;
}
l = initializeAndUpdateDitanceFromRootToNode(head.getLeft(), node);
r = initializeAndUpdateDitanceFromRootToNode(head.getRight(), node);
if(l.getIsFoundNode()){
c.setDistance(l.getDistance() + 1);
c.setIsFoundNode(true);
distance = -(l.getDistance() + 1);
} else if (r.getIsFoundNode()) {
c.setDistance(r.getDistance() + 1);
c.setIsFoundNode(true);
distance = r.getDistance() + 1;
} else {
c.setIsFoundNode(false);
}
head.setDistance(distance);
return c;
}
/*
* This function uses another function printNodesInDistanceKFromRoot and print all the nodes
* that are in distnce k from given node.
*/
public void printNodesInDistanceKFromAGivenNode(TNode head, TNode node, int k){
if(head.equals(node)){
printNodesInDistanceKFromRoot(head, k);
return;
}
if(head.getDistance() < 0){
// Given node is in the left subtree
if(Math.abs(head.getDistance()) == k){
System.out.println("Node value - "+head.getVal());
} else if (Math.abs(head.getDistance()) < k){
printNodesInDistanceKFromRoot(head.getRight(), k-1-(Math.abs(head.getDistance())));
}
printNodesInDistanceKFromAGivenNode(head.getLeft(), node, k);
} else if (head.getDistance() > 0){
// Given node is in the right subtree
if(head.getDistance() == k){
System.out.println("Node value - "+head.getVal());
} else if (head.getDistance() < k){
printNodesInDistanceKFromRoot(head.getLeft(), k-1-head.getDistance());
}
printNodesInDistanceKFromAGivenNode(head.getRight(), node, k);
}
}
/*
* Print all the values nodes with distnce k from the head.
*/
private void printNodesInDistanceKFromRoot(TNode head, int k) {
if(head != null){
if(k == 0){
System.out.println("Node value - "+head.getVal());
return;
} else {
printNodesInDistanceKFromRoot(head.getLeft(), k-1);
printNodesInDistanceKFromRoot(head.getRight(), k-1);
}
}
}
public class TNode {
Integer val;
TNode left;
TNode right;
Integer distance;
public Integer getVal() {
return val;
}
public void setVal(Integer val) {
this.val = val;
}
public TNode getLeft() {
return left;
}
public void setLeft(TNode left) {
this.left = left;
}
public TNode getRight() {
return right;
}
public void setRight(TNode right) {
this.right = right;
}
public Integer getDistance() {
return distance;
}
public void setDistance(Integer distance) {
this.distance = distance;
}
}
public class ReturnStrcture {
private int distance;
private boolean isFoundNode; // 1 for left, 2 for right
public int getDistance() {
return distance;
}
public void setDistance(int distance) {
this.distance = distance;
}
public boolean getIsFoundNode() {
return isFoundNode;
}
public void setIsFoundNode(boolean isFoundNode) {
this.isFoundNode = isFoundNode;
}
}
We shall have to do breadth first scan
- abhishekatuw January 31, 2012For a normal binary tree (not BST), I think we shall to sort node by node value, explicitly by collecting them. Is there anyway to do it directly from in the tree?