## Amazon Interview Question

Member Technical Staffs**Country:**India

**Interview Type:**In-Person

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

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?

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

Can we still go ahead with recursive approach?

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.

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.

Nice to know! I know how to convert a recursion to iteration but not the other way round.

It is time for some studying :)

`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.

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.

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?

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?

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);
}
}
```

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

@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)))

```
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);
}
}
}
```

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;
}
}
```

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.

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;
}
}
}
```

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);
}
}
```

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);

}

}

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) {
Thread t1 = new Thread() {
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);
}
};
Thread t2 = new Thread() {
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 {
Thread.sleep(2000);
} catch(Exception e) {
e.printStackTrace();
}
}
if(root.right != null){
inOrder(root.right);
}
}
}
```

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

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.

- __xy__ February 22, 2014