## Amazon Interview Question for Member Technical Staffs

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem is that your are visiting any node in the trees twice. For explanation, have a look at the following lines you wrote:

``````inOrderTraverse2(node1, node2.getLeft());
System.out.println("  "+node2.getData());
inOrderTraverse2(node1, node2.getRight());``````

Both the calls to inOrderTraverse2 are identical with respect to node1. inOrderTraverse2 is the function which prints node1's contents. So, node1's content will be printed twice.

Comment hidden because of low score. Click to expand.
0

I got the problem but what will be the right solution for this? Can it be done this way?

Comment hidden because of low score. Click to expand.
1
of 1 vote

If it is given that the trees have same structure then I would go for a recursive approach.

A code like this should work:

``````public void alternateTraverse(Node root1, Node root2) {
if (root1 != null && root2 != null) {
alternateTraverse(root1.left, root2.left);
System.out.println("Tree1: " + root1.data);
System.out.println("Tree2: " + root2.data);
alternateTraverse(root1.right, root2.right);
}
}``````

But if they can have different structure, I would do an iterative inorder.

Also, what is the expectation if the trees have different number of nodes?

Comment hidden because of low score. Click to expand.
0

Sorry forgot to mention, trees can have different structure and different number of nodes.

Can we still go ahead with recursive approach?

Comment hidden because of low score. Click to expand.
0

For trees structured differently, I don't think that a recursive solution is possible.
The iterative and recursive approaches differ in only the fact that who maintains the stack of nodes (found but yet to be processed).
In iterative, we maintain an explicit stack.
In recursive, an implicit stack is automatically maintained. All local variables are pushed onto stack when doing a new call and popped when returning from a call.

Now, when we are doing in order traversal, we keep pushing nodes onto stack till we have a left child. If no left child is present, we pop from the stack, visit it and then push the right child. We keep repeating this till the stack becomes empty.

If we have 2 trees with different structures, then we will have cases when we would want to push node for one tree and pop for the other.
This can be done in an iterative program where the stack is explicit and we have full control over it.
But, in recursive approach, for both trees one can do only the same operation (push or pop).
So, a recursive program does not seem possible here.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Theoretically any problem which can be written iteratively can also be written recursively. But in the time-frame of interview it is not possible humanely. Heck, it's not always possible to cover all the cases in recursion even if you have no bounds on time.

They wanted to test you whether you knew iterative traversal without telling you explicitly.

Comment hidden because of low score. Click to expand.
0

Nice to know! I know how to convert a recursion to iteration but not the other way round.
It is time for some studying :)

Comment hidden because of low score. Click to expand.
0

``Theoretically any problem which can be written iteratively can also be written recursively"``

I highly doubt that!
The idea of the recursive tree traversal is that your node stack that you need in an iterative solution is implicitly handled by recursive calls, you put a node on the stack by calling the function again, you pop a node by returning to the calling function.
If you try to handle both trees in the same function you'll come to a point where one tree wants to pop an element from the stack in the iterative solution and the other wants to put yet another element on top of the stack.
Thus in the recursive solution for one tree you have to return from your function and for the other tree you have to make another recursive call! That's not possible.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think a good solution would be to first find the minimum node of each subtree.
after that you can start comparing the values and advance the node which was printed to be its sucssesor.
This does assume the each node has a pointer to his father.
In this approach every node would be visited twice therefore you get linear time complexity and o(1) space complexity.

Comment hidden because of low score. Click to expand.
0

A very costly assumption.

Comment hidden because of low score. Click to expand.
0
of 2 vote

can't we do inorder traversals of the two trees separately in two separate queues and then dequeue and print the data of the nodes alternatively?

Comment hidden because of low score. Click to expand.
0

That will increase the space complexity :).

Comment hidden because of low score. Click to expand.
0
of 0 vote

can't we do inorder traversals of the two trees separately in two separate queues and then dequeue and print the data of the nodes alternatively?

Comment hidden because of low score. Click to expand.
0

That will increase the space complexity :).

Comment hidden because of low score. Click to expand.
0
of 0 vote

Recurse the two trees simultaneously. Essentially, we are printing the nodes at the same level and side in the two trees. It can be easily extended to sum (or any operation on) the corresponding nodes of the two trees.

``````public class InOrder2Trees {

static class Node {
private int data;
private Node leftChild;
private Node rightChild;

public Node(int data) {
this.data = data;
}

public void leftChild(int data) {
this.leftChild = new Node(data);
}

public void rightChild(int data) {
this.rightChild = new Node(data);
}
}

public static void main(String[] args) {
Node root1 = new Node(15);
root1.leftChild(10);
root1.rightChild(20);

Node root2 = new Node(150);
root2.leftChild(100);
root2.rightChild(200);
root2.leftChild.leftChild(50);
root2.rightChild.leftChild(175);
root2.rightChild.rightChild(250);

printInorder(root1, root2);
}

private static void printInorder(Node root1, Node root2) {
if (root1 == null && root2 == null)
return;
Node r1l = root1 == null ? null : root1.leftChild;
Node r2l = root2 == null ? null : root2.leftChild;
printInorder(r1l, r2l);

if (root1 != null)
System.out.println(root1.data);
if (root2 != null)
System.out.println(root2.data);

Node r1r = root1 == null ? null : root1.rightChild;
Node r2r = root2 == null ? null : root2.rightChild;

printInorder(r1r, r2r);
}
}``````

Comment hidden because of low score. Click to expand.
0

Can you please paste the output you got from this code?

Comment hidden because of low score. Click to expand.
0

``````50
10
100
15
150
175
20
200
250``````

Comment hidden because of low score. Click to expand.
0

I doubt if it's going to work.

Comment hidden because of low score. Click to expand.
0

well..copy paste the code and run it yourself

Comment hidden because of low score. Click to expand.
0

@Ankur, are you assuming the trees have the same structure?

Comment hidden because of low score. Click to expand.
0

@m No. Only assuming they both are Binary Trees. In the above example, tree1 has 3 nodes while tree2 has 6

Comment hidden because of low score. Click to expand.
0

@Ankur Do you consider that ...15, 150, 175, 20... is printed alternatively?

Comment hidden because of low score. Click to expand.
0

@m Yes. That's by design. Since the question was unclear on what to do when the trees have different structures, I assumed that we are supposed to print the corresponding nodes alternatively. If you put 10, 15, 20 and 100, 150, 200 in my code, you shall get the same result as mentioned in the question.

Thus, if the two trees have n and m nodes, we will recurse in O (max(n,m) * log (max(n,m)))

Comment hidden because of low score. Click to expand.
0
of 0 vote

The easiest way is to write a inorder tree iterator.

Comment hidden because of low score. Click to expand.
0

But how will you synchronize the iteration?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void inOrderTraversal(BST root) {
if (root != null) {
inOrderTraversal(root.left);
System.out.println(root.num);
inOrderTraversal(root.right);
}
}

void alternateInOrderTraversal(BST root1, BST root2) {
if (root1 != null && root2 != null) {
alternateInOrderTraversal(root1.left, root2.left);
System.out.println(root1.num + " " + root2.num);
alternateInOrderTraversal(root1.right, root2.right);
} else {
if (root1 != null) {
inOrderTraversal(root1);
} else if (root2 != null) {
inOrderTraversal(root2);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

here is an iterative approach,let me know what u guys think

``````public void parrallelInorder(Node root_1, Node root_2) {

Stack<Node> stack_1 = new Stack<Tree.Node>();
Stack<Node> stack_2 = new Stack<Tree.Node>();
Node current_1 = root_1;
Node current_2 = root_2;
boolean done_1 = false;
boolean done_2 = false;
while (!done_1 && !done_2) {

done_1 = iterativeInporder(stack_1, current_1);
done_2 = iterativeInporder(stack_2, current_2);

}

}

public boolean iterativeInporder(Stack<Node> stack, Node current) {
if (current != null) {
stack.push(current);
current = current.leftChild;
return true;
}

else {
if (!stack.isEmpty()) {
Node node = stack.pop();
System.out.println(node.val);
current = current.rightChild;
return true;
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

There are 2 parts to this question in order traversal and printing alternatively. Both cannot be done simultaneously because of the difference in structure and size of the 2 trees.
So lets preprocess the tree first and then print it alternatively. There is a concept of right in threaded tree where each node points to the next in order successor (you can find more online). Once this is done in order traversal in both the trees will be just like traversing through a linked list and hence printing alternatively will be easy.
Now the question is how to convert this tree into a threaded tree. Its a lot easier to construct such a tree from scratch, but in this case we need to convert the current one. Here is a pseudo code for it

``````current = root	//current node
next = NULL	//in order successor
inorder(current, next)
if current == NULL
return
if current->right == NULL	//not linked to the inorder successor
current->right = next	//create the link
threadedFlag[current] = True	//hashmap to keep track of all nodes whose right pointer has been changed as they create loops in the tree.
if current->right == next	//to avoid traversing the loops created in the tree
return
inorder(current->left, current)	//traverse the left subtree
inorder(current->right, next)	//traverse the right subtree``````

I have not implemented this code. But I think it should work. The hashmap is causing space complexity of O(m+n). However its not needed if the intended purpose of tree is only whats mentioned in the problem.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This may not be the cleanest implementation, but it's pretty straight forward.

Given that the tree structures may be different, using a single recursive function is not possible. Instead, we can use an iterative approach modified to iterate through both trees.

Here is an iterative solution of inorder traveral....

``````public static void iterativeInorder(Node n){
Node curr = n;
Stack<Node> s = new Stack<Node>();
while( !s.isEmpty() || curr != null ){
if (curr != null){
s.push(curr);
curr = curr.left;
}
else if(!s.isEmpty()){
curr = s.pop();
curr.print();
curr = curr.right;
break;
}
}
}``````

When we print the the current node, we want the next print to be on the subsequent tree. We can duplicate the same inorder traversal on the second tree just after the print to achieve this. After the second iteration prints, we can break and continue with the first iteration and so on an so forth...

``````public static void iterativeInorderTwoNodes(Node n1, Node n2){

Node curr1 = n1;
Node curr2 = n2;
Stack<Node> s1 = new Stack<Node>();
Stack<Node> s2 = new Stack<Node>();

while(!s1.isEmpty() || curr1 != null){

if (curr1 != null){
s1.push(curr1);
curr1 = curr1.left;
}
else if(!s1.isEmpty()){
curr1 = s1.pop();
curr1.print();

while( !s2.isEmpty() || curr2 != null ){

if (curr2 != null){
s2.push(curr2);
curr2 = curr2.left;
}
else if(!s2.isEmpty()){
curr2 = s2.pop();
curr2.print();
curr2 = curr2.right;
break;
}
}

curr1 = curr1.right;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Three approaches:

1) Using two stacks and simulation in-order traversal using stacks alternately.
2) Using get_next() alternately. Find lowest elements using get_first() at first.
3) Using recursion. Use auxiliary parameter which tells in what tree to recurse.

The first two is trivial. Just have a look at third approach:

``````void print_simultaneously(node * first, node * second, bool left)
{
if (left)
{
if (first->left)
print_simultaneously(first->left, second, !left);

printf("%d ", first->value);

if (first->right)
print_simultaneously(first->right, second, !left);
}
else
{
if (second->left)
print_simultaneously(first, second->left, !left);

printf("%d ", second->value);

if (second->right)
print_simultaneously(first, second->right, !left);
}
}``````

Comment hidden because of low score. Click to expand.
0

In the above code, if one tree has only one node, the other will not be traversed at all.

Comment hidden because of low score. Click to expand.
0
of 0 vote

void inorder(struct Tree1 node_tree1, struct Tree2 node_tree2, int bool)
{
if((node_tree1 != null) && (found == 0))
{
inorder(node_tree1->left,node_tree2,1);
printf("%d",node_tree1->data);
inorder(node_tree1->right,node_tree2,1);
}
if((node_tree2 != null) && (found == 1))
{
inorder(node_tree1,node_tree2->left,0);
printf("%d",node_tree2->data);
inorder(node_tree,node_tree2->right,0);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I suppose we can do this:
(1)inorder traverse and transform each tree into a linked list
(2)print the two linked lists alternately

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think what we can do is search for the smallest element in both tree
And after that keep on calling inorder successor for both of them alternatively until you reach the largest element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution: I used threads to keep track of printing one by one thread, it uses recursive inorder traversal synchronized block.

Assumptions:
Tree need not to be same level - meaning both tree can hold different number of nodes and can differ in number of levels.

``````public static void main(String[] args) {

public void run() {
TreeCheck tc = new TreeCheck();
Node tree1 = new Node(20, new Node(10), new Node(40, new Node(30), null));
tc.inOrder(tree1);
}
};
public void run() {
TreeCheck tc = new TreeCheck();
Node tree2 = new Node(80, new Node(60, new Node(50), new Node(70)), new Node(86, new Node(82), new Node(90)));
tc.inOrder(tree2);
}
};

t1.start();
t2.start();

}

public void inOrder(Node root) {

if(root.left != null){
inOrder(root.left);
}

synchronized(this) {
System.out.println(root.data);
try {
} catch(Exception e) {
e.printStackTrace();
}
}

if(root.right != null){
inOrder(root.right);
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.