CareerCup

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.

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

The easiest way is to write a inorder tree iterator.

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

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

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.

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