CareerCup

struct node {
    int val;
    node *left,*right;
    node(int v):val(v),left(0),right(0) {}
};

class bst_iterator {
private:
    stack<node *> s;
public:
    bst_iterator(node *rt) {
        while (rt)
            s.push(rt),rt=rt->left;
    }
    bool has_next() {
        return !s.empty();
    }
    node *next() {
        node *c=s.top();
        s.pop();
        node *n=c->right;
        while (n)
            s.push(n),n=n->left;
        return c;
    }
};

bool same_inorder(node *a,node *b) {
    bst_iterator ita(a),itb(b);
    while (ita.has_next()&&itb.has_next()) {
        node *ca=ita.next();
        node *cb=itb.next();
        if (ca->val!=cb->val)
            return false;
    }
    return !ita.has_next()&&!itb.has_next();
}

var Node = function (value) {
	this.value = value;
};

function StepTree(v) {
	var S = [];
	S.push(v);

	return {
		next: function () {
			while (S.length && S[S.length - 1].visited !== true) {
				v = S.pop();
				if (!v.visited) {
					v.visited = true;
					v.right && S.push(v.right);
					S.push(v);
					v.left && S.push(v.left);
				}
			} 
			return S.pop() || null;
		}
	};
}


function isSame(node1, node2) {
	return node1.value === node2.value;
}
function compareInorder(tree1, tree2) {
	tree1 = StepTree(tree1);
	tree2 = StepTree(tree2);

	var bool = true;
	var node1 = tree1.next();
	var node2 = tree2.next();
	
	while (bool && (node1 || node2)) {
		bool = isSame(node1, node2);
		node1 = tree1.next();
		node2 = tree2.next();
	}

	return bool;
}

var aA = new Node('A');
var aB = new Node('B');
var aC = new Node('C');
var bA = new Node('A');
var bB = new Node('B');
var bC = new Node('C');
aB.right = aA;
aB.left = aC;

bA.right = bB;
bB.right = bC;

compareInorder(aB, bA);

Node class

package binaryTree;

public class Node<T> {
	public T getData() {
		return data;
	}
	public void setData(T data) {
		this.data = data;
	}
	public Node<T> getLeft() {
		return left;
	}
	public void setLeft(Node<T> left) {
		this.left = left;
	}
	public Node<T> getRight() {
		return right;
	}
	public void setRight(Node<T> right) {
		this.right = right;
	}
	private T data;
	private Node<T> left;
	private Node<T> right;
}

package binaryTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class Tree<T> {
	Node<T> root;
	
	public Tree(){
		
	}
	public Node<T> getRoot(){
		return root;
	}
	public void setRoot(T data){
		root = new Node<T>();
		root.setData(data);
	}
	
	public void addLeftChild(T par, T chld){
		Node<T> parNode = getNode(par);
		if(parNode != null){
			Node<T> leftNode = parNode.getLeft();
			if(leftNode == null){
				leftNode = new Node<T>();
				parNode.setLeft(leftNode);
			}
			leftNode.setData(chld);
		}
	}
	
	public void addRightChild(T par, T chld){
		Node<T> parNode = getNode(par);
		if(parNode != null){
			Node<T> rightNode = parNode.getRight();
			if(rightNode == null){
				rightNode = new Node<T>();
				parNode.setRight(rightNode);
			}
			rightNode.setData(chld);
		}
	}
	
	public Node<T> getNode(T data){
		return getNode(getRoot(), data);
	}
	public Node<T> getNode(Node<T> node, T data){
		if(node != null){
			if(node.getData().equals(data)){
				return node;
			}
			Node<T> leftNodeResult = getNode(node.getLeft(),data);
			if(leftNodeResult != null){
				return leftNodeResult;
			}
			Node<T> rightNodeResult = getNode(node.getRight(),data);
			if(rightNodeResult != null){
				return rightNodeResult;
			}
		}
		return null;
	}
	
	public void inOrder(Node<T> node,List<T> list){
		if(node != null){
			if(node.getLeft() != null){
				inOrder(node.getLeft(),list);
			}
			list.add(node.getData());
			if(node.getRight() != null){
				inOrder(node.getRight(),list);
			}
		}
	}
	
	public List<T> inOrder(){
		List<T> list = new ArrayList<T>();
		inOrder(root,list);
		return list;
	}
	
	public boolean isSameInorder(Tree<T> other){
		Iterator<T> thisListIter = inOrder().iterator();
		Iterator<T> otherListIter = other.inOrder().iterator();
		while(thisListIter.hasNext() && otherListIter.hasNext()){
			if (thisListIter.next() != otherListIter.next()){
				return false;
			}
		}
		if(thisListIter.hasNext() || otherListIter.hasNext()){
			return false;
		}
		return true;
	}
}

Test code

package binaryTree;


public class SameInorder {
	public static void main(String[] args){
		Tree<String> t1 = new Tree<String>();
		t1.setRoot("B");
		t1.addLeftChild("B", "A");
		t1.addRightChild("B", "C");
		
		
		Tree<String> t3 = new Tree<String>();
		t3.setRoot("A");
		t3.addRightChild("A", "B");
		t3.addRightChild("B", "C");
		
		System.out.println(t1.isSameInorder(t3));
	}
}

public class Node{
private int value;
private Node left;
private Node right;

public Node(int v)
{
this.value=v;
}
public Node(int v,Node l,Node r)
{
this.value=v;
this.left=l
this.right=r;
}
}


public class InOrderAssessor{


public boolean checkInOrder(Node a,Node b)
{
if(a==null && b==null)
{
return true;
}

String x=getInOrderString(a,"");
String y=getInOrderString(b,"");
return x.equals(y);
}


private void getInOrder(Node n,String s)
{
if(n==null)
{
return;
}
getInOrder(n.left.mp);
s+=n.value();
getInOrder(n.right,mp);
}


}

Iterative in-order traversal will solve the problem.
have a method getNext(), which returns the next node value in in-order traversal. Use this value to compare the traversals of the trees.
getNext() can be implemented using a stack.

struct node {
    int val;
    node *left,*right;
    node(int v):val(v),left(0),right(0) {}
};

class bst_iterator {
private:
    stack<node *> s;
public:
    bst_iterator(node *rt) {
        while (rt)
            s.push(rt),rt=rt->left;
    }
    bool has_next() {
        return !s.empty();
    }
    node *next() {
        node *c=s.top();
        s.pop();
        node *n=c->right;
        while (n)
            s.push(n),n=n->left;
        return c;
    }
};

bool same_inorder(node *a,node *b) {
    bst_iterator ita(a),itb(b);
    while (ita.has_next()&&itb.has_next()) {
        node *ca=ita.next();
        node *cb=itb.next();
        if (ca->val!=cb->val)
            return false;
    }
    return !ita.has_next()&&!itb.has_next();
}

Hey guys!
I've tried to make the compact OOP code for this problem using an InOrderIterator. Check it out:

public class SameInorderGoogle {

    private static class TreeNode {
        public final int val;
        public TreeNode left, right;
        public TreeNode(int val) { this.val = val; }
    }

    private static class InOrderIterator implements Iterator<TreeNode> {
        private TreeNode curr;
        private Deque<TreeNode> stack = new LinkedList<>();
        public InOrderIterator(TreeNode root) { this.curr = root; }

        @Override public TreeNode next() {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode ret = stack.pop();
            curr = ret.right;
            return ret;
        }

        @Override public boolean hasNext() {
            return curr != null || !stack.isEmpty();
        }
    }

    public boolean compareInOrder(TreeNode r1, TreeNode r2) {
        InOrderIterator iterator1 = new InOrderIterator(r1);
        InOrderIterator iterator2 = new InOrderIterator(r2);
        while (iterator1.hasNext() && iterator2.hasNext())
            if (iterator1.next().val != iterator2.next().val) return false;
        return true;
    }
}

Inorder iterator class with the driver function to compare output for both iterator.

package prep;

import java.util.Stack;

public class InorderIterator {
	Stack<Node> st = new Stack<Node>();
	Node root;
	Node nextNode = null;
	
	public InorderIterator(Node root) {
		this.root = root;
	}
	
	public boolean hasnext(){
		if(nextNode != null) return true;
		Node cur = null;
		if(st == null) return false;
		if(!st.empty())
			cur = st.pop();
		else{
			cur = root;
		}
		while(true){
			if(cur != null){
				st.push(cur);
				cur = cur.left;
			}else{
				if(!st.isEmpty()){
					Node tmp = st.pop();
					if(nextNode == null){
						nextNode = tmp;
					}
					st.push(tmp.right);
					tmp = tmp.right;
					return true;
				}else{
					st= null;
					return false;
				}
			}
		}
	}
	
	public Node next(){
		if(nextNode != null){
			Node tmp = nextNode;
			nextNode = null;
			return tmp;
		}
		if(hasnext()){
			Node tmp = nextNode;
			nextNode = null;
			return tmp;
		}else{
			new Exception("Element not found");
		}
		
		return nextNode;
	}
}

public boolean sameInorder(Node root1,Node root2){
    	   	InorderIterator itr1 = new InorderIterator(root1);
    	   	InorderIterator itr2 = new InorderIterator(root2);
	   		while(itr1.hasnext() && itr2.hasnext()){
	   			if(itr1.next().value != itr2.next().value){
	   				return false;
	   			}
	   		}
	   		if((!itr1.hasnext() && itr2.hasnext()) || (itr1.hasnext() && !itr2.hasnext())){
	   			return false;
	   		}
	   		return true;
       }

bool compare(Node *a, Node *b) {

	stack<Node*> x, y;
	// Find the first elements
	while (a) {
		x.push(a);
		a = a->left;
	}
	while (b) {
		y.push(b);
		b = b->left;
	}
	// Walk the trees
	while (!x.empty() && !y.empty()) {
		a = x.top(); x.pop();
		b = y.top(); y.pop();

		if (a->value != b->value) {
			return false;
		}
		// Find next node on tree a
		if (a->right) x.push(a = a->right);
		while (a->left) {
			x.push(a = a->left);
		}
		// Find next node on tree b
		if (b->right) y.push(b = b->right);
		while (b->left) {
			y.push(b = b->left);
		}
	}
	return x.empty() && y.empty();
}

Do inorder traversal for both tree and keep the output in a queue. When trying to add item from inorder of first tree check if output from second queue is empty. If queue is not empty, remove that item from second queue.
Worst case O(m + n) : Both tree fully traversed and Best case: O(max(log m, log n)) : First item in the tree don't match.

Code:
public <T> boolean inorder(Util.Tree<T> t1, Util.Tree<T> t2, Queue<T> res1, Queue<T> res2) {
if (t1 == null && t2 == null) {
return true;
}
if (!inorder((t1 != null ? t1.left : null), (t2 != null ? t2.left : null), res1, res2)) {
return false;
}
if (t1 != null) {
if (!add(t1.value, res1, res2)) {
return false;
}
}
if (t2 != null) {
if (!add(t2.value, res2, res1)) {
return false;
}
}
if (!inorder((t1 != null ? t1.right : null), (t2 != null ? t2.right : null), res1, res2)) {
return false;
}
return true;
}

public <T> boolean solve(Util.Tree<T> t1, Util.Tree<T> t2) {
LinkedTransferQueue<T> res1 = new LinkedTransferQueue<T>();
LinkedTransferQueue<T> res2 = new LinkedTransferQueue<T>();
return inorder(t1, t2, res1, res2) && res1.isEmpty() && res2.isEmpty();
}

boolean isSameInorder(b1,  b2)
{
	stack : s1;
	stack : s2;
	while(b1 ! =null)
	{
		s1.push(b1);
		b1 =b1.left;
	}


	while(b2 ! =null)
	{
		s2.push(b2);
		b2 =b2.left;
	}

	while((s1 && s2 )!=null)
	{
		node a = s1.pop();
		node b = s2.pop();
		if(a.data == b.data)
		{
			return false;
		}
		a = a.right;
		b = b.right;
		while(a!=null)
		{
			s1.push(a);
			a = a.left;
		}

		while(b!=null)
		{
			s2.push(b);
			b = b.left;
		}
	}
	return true;
}

int isSameInorder(Node* root1, Node* root2){
	Stack<Node*> st1,st2;
	Node* iter1=root1;
	Node* iter2=root2;
	do{
		while(iter1!=NULL){
		  st1.push(iter1);
		  iter1=iter1->left;
		}
		while(iter2!=NULL){
		  st2.push(iter2);
		  iter2=iter2->left;
		}
		Node* temp1 = st1.pop();
		Node* temp2 = st2.pop();
		if(temp1->value != temp2->value) return false;
		iter1=temp1->right;
		iter2=temp2->right;
	}while(!st1.empty() && ! st2.empty());
	if(st1.empty() && st2.empty())
		return true;
	else
		return false;
}

Usually we use Stack to do iterative InOrder traversal. With 2 binary trees, we certainly have to use at least 2 stacks.
The each tree has its own traversal steps, the order of PUSH a node in the corresponding stack will not be the same. However, in oder to have the same InOrder, the POP from the corresponding stack must be in the same order.

So, we can use a variable to keep track of that. Iteratively traversal Tree1 only if the variable is null and stop every time a Node is poped out of Stack1. Start traversal the Tree2 from there until a Node is poped out, if it's the same as the Node from Tree1, set the variable to null again.

Something like this:

public static boolean check(Node root1, Node root2) {
		Stack<Node> stack1 = new Stack<Node>();
		Node current1 = root1;
		
		Stack<Node> stack2 = new Stack<Node>();
		Node current2 = root2;
		
		Node popedNode = null;
		
		while(true) {
			if(popedNode == null) {
				if(current1 != null) {
					stack1.push(current1);
					current1 = current1.left;
				} else {
					if(!stack1.isEmpty()) {
						popedNode = stack1.pop();
						current1 = popedNode.right;
					} else {
						break;
					}
				}
			} else { //popedNode != null, has been assigned above
				if(current2 != null) {
					stack2.push(current2);
					current2 = current2.left;
				} else {
					if(!stack2.isEmpty()) {
						Node n = stack2.pop();
						if(n.value == popedNode.value) {
							System.out.println(n.value);
							popedNode = null; //continue travel Tree1
						}
						else
							return false;
						current2 = n.right;
					} else {
						break;
					}
				}
			}
			
			
		}

		if(!stack1.isEmpty() || stack2.isEmpty())
				return false;
		return true;
	}

Approach: Keep two List for Inorder traversal of each tree. Traverse both tree in inorder parallel and keep updating the inorder list. Whenever adding new element, check top of the small is same to corresponding larger list. Break early whenever inorder is not same.
In the worst case list size will grow as many number of nodes in both tree.
In best case it will detect as early possible without much memory usage.

Here is the C# code with Test driver

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// Given two binary trees ( not BST) ,   return true if both of them have same inorder  else return false.
    /// Approach: Keep to List for Inorder traversal of each tree. Whenver adding new element, check top of the small is same to corresponding larger list.
    /// Break early whenever inorder is not same. In the worst case list size will grow as many number of nodes in both tree. 
    /// In best case it will detect as early possible without memory usage.
    /// Author: Pramod Kumar Chandoria
    /// </summary>
    public class Node
    {
        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }

        public Node left;
        public Node right;
        public int data;
    }
    public class SimilarInorderTree
    {
        public static void Main(string[] args)
        {
            var areSame = SimilarInorderTree.TreeWithSameInorder(null, null);
            Console.WriteLine("Null tree expected same, actual result is:" + areSame);

            Node tree1 = new Node(5);
            Node tree2 = new Node(5);
            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree with only 1 same node are expected same, actual result is:" + areSame);

            tree1 = new Node(4);
            tree1.left = new Node(2);
            tree1.right = new Node(6);
            tree1.left.left = new Node(1);
            tree1.left.right = new Node(3);

            tree2 = new Node(3);
            tree2.left = new Node(2);
            tree2.right = new Node(4);
            tree2.left.left = new Node(1);
            tree2.right.right = new Node(6);

            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree with same Inorder, but not same structure are expected same, actual result is:" + areSame);

            tree1 = new Node(4);
            tree1.left = new Node(2);
            tree1.right = new Node(6);
            tree1.left.left = new Node(1);
            tree1.left.right = new Node(3);

            tree2 = new Node(3);
            tree2.left = new Node(2);
            tree2.right = new Node(4);
            tree2.left.left = new Node(6);
            tree2.right.right = new Node(6);

            areSame = SimilarInorderTree.TreeWithSameInorder(tree1, tree2);
            Console.WriteLine("Two tree NOT same Inorder, are expected NOT same, actual result is:" + areSame);

    
        }

        //
        public static bool TreeWithSameInorder(Node tree1, Node tree2)
        {
            IList<int> inOrder1 = new List<int>();
            IList<int> inOrder2 = new List<int>();
            return SameInorder(tree1, tree2, inOrder1, inOrder2) && inOrder1.Count == inOrder2.Count;
        }

        internal static bool SameInorder(Node tree1, Node tree2, IList<int> inOrder1, IList<int> inOrder2)
        {
            
            int topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);
            
            if (tree1 == null && tree2 == null)
            {
               return topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
            }

            bool isMinTopSame = false;
            if (tree1 != null && tree2 != null)
            {
                if (!SameInorder(tree1.left, tree2.left, inOrder1, inOrder2))
                {
                    return false;
                }

                //topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);

                //isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
                //if(!isMinTopSame)
                //{
                //    return false;
                //}

                inOrder1.Add(tree1.data);
                inOrder2.Add(tree2.data);
                topIndex = Math.Min(inOrder1.Count - 1, inOrder2.Count - 1);
                //topIndex++;
                isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
                if (!isMinTopSame)
                {
                    return false;
                }

                return SameInorder(tree1.right, tree2.right, inOrder1, inOrder2);
            }

            // One tree is null;
            isMinTopSame = tree1 != null ? SameInorder(tree1.left, null, inOrder1, inOrder2) : SameInorder(null, tree2.left, inOrder1, inOrder2);
                
            if (!isMinTopSame)
            {
                return false;
            }
                
            if (tree1 != null) 
            {
                inOrder1.Add(tree1.data);
            } 
            else 
            {
                inOrder2.Add(tree2.data);
            }

            topIndex = Math.Min(inOrder1.Count -1, inOrder2.Count -1);
            isMinTopSame = topIndex < 0 || inOrder1[topIndex] == inOrder2[topIndex];
            if (!isMinTopSame)
            {
                return false;
            }

            return (tree1 != null ? SameInorder(tree1.right, null, inOrder1, inOrder2) : SameInorder(null, tree2.right, inOrder1, inOrder2));
        }

    }
}

public static boolean inordertest(Node node1, Node node2){
        Bool flag=new Bool(true);
        inordertest(node1, node2, flag);
        return flag.val;
    }
   
    private static void inordertest(Node node1, Node node2, Bool flag){
   	if(node1==null && node2==null){
	    return;
	}
	if(node1==null || node2 == null){
	    flag.val=false;
	    return;
	}
	inordertest(node1.leftChild, node2.leftChild, flag);
	if(node1.data != node2.data){
	    flag.val=false;
		return;
	}
	inordertest(node1.rightChild, node2.rightChild, flag);
} 

    public static class Bool{
         boolean val;
         public Bool(boolean val){
             this.val=val;
         }
     }

typedef struct _node {
	int val;
	struct _node *ln;
	struct _node *rn;
}Node;

int
_isinordersame(Node *t1, Node *t2)
{
	Node *stack1[1000]={NULL};
	Node *stack2[1000]={NULL};
	int top1=-1, prev1=-1;
	int top2=-1, prev2=-1;
	int s1[1000]={-1}, s2[1000]={-1}, last1=-1, last2=-1;
	int same = 1;

	while(t1 || t2) {
		if(t1) {
			if (prev1!=t1->val && t1->ln) {
				stack1[++top1] = t1;
				t1 = t1->ln;
			} else {
				s1[++last1] = t1->val;
				if (t1->rn) t1 = t1->rn;
				else if (top1>=0) {
					t1 = stack1[top1--];
					prev1 = t1->val;
				}
				else t1 = NULL;
			}
		}
		if(t2) {
			if (prev2!=t2->val && t2->ln) {
				stack2[++top2] = t2;
				t2 = t2->ln;
			} else {
				s2[++last2] = t2->val;
				if (t2->rn) t2 = t2->rn;
				else if (top2>=0) {
					t2 = stack2[top2--];
					prev2 = t2->val;
				}
				else t2 = NULL;
			}
		}

		if (last1>=0 && last2>=0) {
			int min = (last1>last2)?last2:last1;
			while(min>=0) {
				if(s1[min]!=s2[min]) {
					same = 0;
					break;
				}
				min--;
			}
			min = (last1>last2)?last2:last1;
			if(last1-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last1-min);i++) s1[i] = s1[k];
			}
			if(last2-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last2-min);i++) s2[i] = s2[k];
			}
			last1 -= min+1;
			last2 -= min+1;
		}
	}
	return same;
}

typedef struct _node {
	int val;
	struct _node *ln;
	struct _node *rn;
	struct _node *pn;
}Node;
int
_isinordersame(Node *t1, Node *t2)
{
	Node *stack1[1000]={NULL};
	Node *stack2[1000]={NULL};
	int top1=-1, prev1=-1;
	int top2=-1, prev2=-1;
	int s1[1000]={-1}, s2[1000]={-1}, last1=-1, last2=-1;
	int same = 1;

	while(t1 || t2) {
		if(t1) {
			if (prev1!=t1->val && t1->ln) {
				stack1[++top1] = t1;
				t1 = t1->ln;
			} else {
				s1[++last1] = t1->val;
				if (t1->rn) t1 = t1->rn;
				else if (top1>=0) {
					t1 = stack1[top1--];
					prev1 = t1->val;
				}
				else t1 = NULL;
			}
		}
		if(t2) {
			if (prev2!=t2->val && t2->ln) {
				stack2[++top2] = t2;
				t2 = t2->ln;
			} else {
				s2[++last2] = t2->val;
				if (t2->rn) t2 = t2->rn;
				else if (top2>=0) {
					t2 = stack2[top2--];
					prev2 = t2->val;
				}
				else t2 = NULL;
			}
		}

		if (last1>=0 && last2>=0) {
			int min = (last1>last2)?last2:last1;
			while(min>=0) {
				if(s1[min]!=s2[min]) {
					same = 0;
					break;
				}
				min--;
			}
			min = (last1>last2)?last2:last1;
			if(last1-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last1-min);i++) s1[i] = s1[k];
			}
			if(last2-min>0) {
				int i=0,k;
				for(i=0,k=min+1;i<(last2-min);i++) s2[i] = s2[k];
			}
			last1 -= min+1;
			last2 -= min+1;
		}
	}
	return same;
}

This is probably the worst possible way of implementing it unless you really wanted to learn the C++ 11 thread synchronization stuff really badly which is why I did it this way.

// Tree_Match.h
#include <istream>
#include <iostream>

#include <mutex>
#include <thread>
#include <functional>     // std::ref
#include <future>         // std::promise, std::future
using namespace std;

#pragma once 


class Matchup
{
public:
	Matchup()
	{
		lock.lock();
		state = START;
		lock.unlock();
		fut = new std::future < bool > ; // these miserable things cannot be reused so we will be continually deleting and replacing them 
		matched = new std::promise < bool > ;
	}//-----------------------------------------------------

	~Matchup()
	{
		delete fut;
		delete matched;
	}//-----------------------------------------------------

	bool ok()
	{
		lock.lock();
		bool out = (state == START);
		lock.unlock();
		return out;
	}//-----------------------------------------------------
	
	bool put(int v)
	{
		lock.lock();

		switch (state)
		{
		case START:
		{
			value = v;
			state = WAITING_FOR_OTHER;
			*fut = matched->get_future();
			lock.unlock();

			bool out = fut->get();

			lock.lock();  // you can not reuse a future or probabaly a promise so we will just delete them and get new ones   
			delete matched;
			delete fut;
			fut = new std::future < bool >;
			matched = new std::promise < bool >;
			lock.unlock();
			
			return out;
		}

		case WAITING_FOR_OTHER:
		{
			bool m = (v == value);
			matched->set_value(m);
			state = m ? START : FAIL;
			lock.unlock();
			return m;
		}
		case FAIL:
			lock.unlock();
			return false;

		case DONE:
			lock.unlock();
			return false;
		}

		return false;
	}//-----------------------------------------------------

	void done()
	{
		lock.lock();

		if (WAITING_FOR_OTHER == state)
		{
			matched->set_value(false);
			state = FAIL;
		}
		else
		{
			state = DONE;
		}

		lock.unlock();
	}//-----------------------------------------------------


private:

	std::mutex lock;

	enum State { START, WAITING_FOR_OTHER, FAIL, DONE };
	//std::thread::id owner;
	State state;
	int value;
	std::promise<bool> *matched;
	std::future<bool> *fut;
};


class Node
{
public:
	Node()
	{
		left = nullptr;
		right = nullptr;
		data = 0;
	}//----------------------------------------------------------------------
	
	Node(Node *l, int i, Node *r = nullptr)
	{
		left = l;
		right = r;
		data = i;
	}//----------------------------------------------------------------------

	Node(int i, Node *r = nullptr)
	{
		left = nullptr;
		right = r;
		data = i;
	}//----------------------------------------------------------------------
	
	~Node()
	{
		if (left != nullptr)
		{
			delete left;
		}

		if (right != nullptr)
		{
			delete right;
		}
	}//----------------------------------------------------------------------

	void inorder_dump()const
	{
		if (left != nullptr)
		{
			left->inorder_dump();
		}

		cout << data << " ";

		if (right != nullptr)
		{
			right->inorder_dump();
		}
	}//----------------------------------------------------------------------
	
	Node *left;
	Node *right;
	int data;
};

other file 

#include "stdafx.h"
#include <string>
#include <thread>
#include <mutex>
#include <istream>
#include <iostream>
using namespace std;
#include "Tree_Match.h"

std::mutex print_lock;




void tree_comp_thread_r(Node *r, Matchup *match)
{
	if (r->left != nullptr)
	{
		tree_comp_thread_r(r->left, match);
	}

	print_lock.lock();

	cout << std::this_thread::get_id() << " " << r->data << "\n";

	print_lock.unlock();



	bool m = match->put(r->data);

	if (!m)
	{
		return;
	}

	print_lock.lock();

	cout << std::this_thread::get_id() << " " << r->data << " " << m << "\n";

	print_lock.unlock();

	if (r->right != nullptr)
	{
		tree_comp_thread_r(r->right, match);
	}
}


void tree_comp_thread(Node *r, Matchup *match)
{
	tree_comp_thread_r(r, match); // we wrap this to deal with the case when the trees are of differing size
	match->done();
}


int _tmain(int argc, _TCHAR* argv[])
{

	//Node *a = new Node(new Node(new Node(1), 2), 3, new Node(new Node(new Node(4),5), 6));
		         

	//Node *b = new Node(1, new Node(2, new Node(new Node(3), 4, new Node(new Node(5), 6))));

	Node *a = new Node(new Node(1), 2);
	Node *b = new Node(1);


	a->inorder_dump();
	cout << "\n";
	b->inorder_dump();
	cout << "\n";

	Matchup match;

	thread ta = thread(tree_comp_thread, a, &match);
	thread tb = thread(tree_comp_thread, b, &match);

	ta.join();
	tb.join();


	if (match.ok())
	{
		cout << "thay matched\n";
	}
	else
	{
		cout << "thay did not match\n";
	}


}

notes on the earlier code

I could not find a release and sleep function in the C++ 11 libraries. Instead I found this thing where you have objects called promises and futures. You can use a 'promise' object to create a 'future' object.
fut = prom.get_future()
If you try to get the value out of the future object it will block until you push a value into the promise object
val = fut.get(); // if the promise has not had a value pushed into it at this point the current thread will sleep here until some other thread pushes a value into the promise object
in the other thread you call this:
prom.set_value(m);
wakes up the sleeping thread and the value from m is not put into val
unfortunately it looks like you cannot reuse these things.
So I cannot do this a second time. I may be missing something. So I ended up using pointers and deleting and reallocating new objects every time around. Probably this will have some pretty hefty overhead.
Never the lass this mechanism in general seems like it might have some really interesting uses.
A'

An implementation to compare objects without using stack

static boolean checkInOrder(Node root1, Node root2) {
		
		InOrderIterator ita1 = new InOrderIterator(root1);
		InOrderIterator ita2 = new InOrderIterator(root2);
		
		while(ita1.hasNext() || ita2.hasNext()){
			Node node1 = ita1.next();
			Node node2 = ita2.next();
			
			if(node1 == null || node2 == null) {
				return false;
			}
		
			if(node1.value != node2.value)
				return false;
		}
		return true;
	}


	static class InOrderIterator {
		Node root;
		
		InOrderIterator(Node root){
			this.root = root;
		}
		
		boolean hasNext() {
			return root != null?true:false;
		}
		
		Node next() {
			Node next = null;
			while(root != null) {
				if(root.left == null){
					next = root;
					root = root.right;
					break;
				} else {
					Node temp = root.left;
					while(temp.right != null && temp.right != root) {
						temp = temp.right;
					}
					if(temp.right == null) {
						temp.right = root;
						root = root.left;
					} else {
						next = temp.right;
						temp.right = null;
						root = root.right;
						break;
					}
				}
			}
			return next;
			
		}
	}

public boolean isSameInorder(Node root1,Node root2)
{
Stack<Node> stk1 = new Stack<Node>();
Stack<Node> stk2 = new Stack<Node>();

boolean ret = true;
boolean comparing = true;

stk1.push(root1.left);
stk1.push(root2.left);

while(comparing)
{

while(root1.left!=null){
stk1.push(root1.left);
root1 = root1.left;
}

while(root2.left!=null){
stk1.push(root2.left);
root2 = root2.left;
}

while(true)
{
Node n1 = stk1.pop();
Node n2 = stk2.pop();

if(n1.data!=n2.data)
{
ret = false;
comparing = false;
break;
}
else if(n1.right!=null && n2.right!=null)
{
stk1.push(n1.right);
stk2.push(n2.right);

root1= n1.right;
root2= n2.right;
break;
}else
{
continue;
}
}

}
return ret;
}

public boolean isSameInorder(Node root1,Node root2)
{
	Stack<Node> stk1 = new Stack<Node>();
	Stack<Node> stk2 = new Stack<Node>();
	
	boolean ret = true;
	boolean comparing = true;
	
	stk1.push(root1.left);
	stk1.push(root2.left);
	
	while(comparing)
	{
	
		while(root1.left!=null){
			stk1.push(root1.left);
			root1 = root1.left;
		}
			
		while(root2.left!=null){
			stk1.push(root2.left);
			root2 = root2.left;
		}
	
	while(true)
	{
		Node n1 = stk1.pop();
		Node n2 = stk2.pop();
		
		if(n1.data!=n2.data)
		{
			ret = false;
			comparing = false;
			break;
		}
		else if(n1.right!=null && n2.right!=null)
		{
			stk1.push(n1.right);
			stk2.push(n2.right);

			root1= n1.right;
			root2= n2.right;
			break;
		}else
		{
			continue;
		}
	}
	
	}
	return ret;
}

public static boolean isSameInOrder(Tree t1, Tree t2){

		boolean isTrue=false;
		
		if(t1.value==t2.value){
			isTrue=true;

			if(t1.leftTree!=null && t2.leftTree!=null ){

				isTrue = isSameInOrder(t1.leftTree,t2.leftTree);
			
			}

			if(t1.rightTree!=null && t2.rightTree!=null ){
				
				isTrue = isSameInOrder(t1.rightTree,t2.rightTree);
			
			}

		}
		else{
			isTrue=false;
		}

		return isTrue;

	}

Use a stack to do an in-order traversal of both trees. Usual single-tree In-order traversals add on left child until it's NULL, then visit the parent, then recurse right. This algorithm recurses left down the first tree until it finds the NULL child, then pauses as the parent so that it can then do the same with the second tree. One this next "in-order" Node is found, the two are compared. If they are different, we return false. If they are the same, we keep going, recursing right.

struct Node {
	Node* left;
	Node* right;
	char data;
};

bool treesHaveSameInorder(Node* root1, Node* root2) {
    if( (!root1 && root2) || (root1 && !root2) ) return false;
    if(root1 && root2) return true;
    stack<Node*> s1, s2;
    s1.push(root1);
    s2.push(root2);
    Node* trav1 = root1->left;
    Node* trav2 = root2->left;
    while(!s1.empty() && !s2.empty()) {
        while(trav1) {
            s1.push(trav1);
            trav1 = trav1->left;
        }
        trav1 = s1.top();
        s1.pop();
        while(trav2) {
            s2.push(trav2);
            trav2 = trav2->left;
        }
        trav2 = s2.top();
        s2.pop();
        if(trav1->data != trav2->data) return false;
        trav1 = trav1->right;
        trav2 = trav2->right;
    }
    if(!s1.empty() || !s2.empty()) return false;
    return true;
}

Create a class BSTInOrderIterator

class BSTInOrderIterator {
BSTNode root;
Stack<BSTNode> s;
public BSTInOrderIterator(BSTNode root) {}
boolean hasNext();
BSTNode next();
}
just implement the inorder traversal in iterator.

Then you can initializes two instance and compare.

This is my java code :

class Nodecomp{
	Nodecomp left, right;
	int data;
	Nodecomp(int x){
		data=x;
	}
}
public class CompareInorder {

	Nodecomp root;
	boolean InOrder(Nodecomp node1, Nodecomp node2){
		Stack<Nodecomp> stack=new Stack<Nodecomp>();
		Stack<Nodecomp> stack2=new Stack<Nodecomp>();
		Nodecomp n=node1;
		Nodecomp n2=node2;
		if(n==null||n2==null)
			return false;
		while(n!=null){
			stack.push(n);
			n=n.left;
		}
		while(n2!=null){
			stack2.push(n2);
			n2=n2.left;
		}
		
		while(stack.size()>0&&stack2.size()>0){
			n=stack.pop();
			n2=stack2.pop();
			if(n.data!=n2.data){
				return false;
			}
			if(n.right!=null){
				n=n.right;
				while(n!=null){
					stack.add(n);
					n=n.left;
					
				}
			}
			if(n2.right!=null){
				n2=n2.right;
				while(n2!=null){
					stack2.add(n2);
					n2=n2.left;
					
				}
			}
		}
		return true;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CompareInorder tree=new CompareInorder();
		tree.root=new Nodecomp(1);
		tree.root.left=new Nodecomp(2);
		tree.root.right=new Nodecomp(3);
		CompareInorder tree1=new CompareInorder();
		
		tree1.root=new Nodecomp(2);
		tree1.root.right=new Nodecomp(1);
		tree1.root.right.right=new Nodecomp(3);
		System.out.println("Are they equal :"+tree1.InOrder(tree.root, tree1.root));
	}

}

private static boolean testInOrderStack(TreeNode tree1, TreeNode tree2) throws Exception {
		Stack<TreeNode> stack1 = new Stack<TreeNode>(5);
		Stack<TreeNode> stack2 = new Stack<TreeNode>(5);
		Stack<TreeNode> result = new Stack<TreeNode>(5);
		// push root
		stack1.push(tree1);
		stack2.push(tree2);
		// hash set to mark roots that are visited
		Set<TreeNode> set1 = new HashSet<TreeNode>();
		Set<TreeNode> set2 = new HashSet<TreeNode>();
		while (!stack1.isEmpty() && !stack2.isEmpty()) {
			/* wait until the first push to the result stack that
			 * stores the in order traversal of the first tree.
			 */
			boolean waitTree1 = true;
			while(waitTree1) {
				TreeNode root1 = stack1.pop();
				// if already visited root or a leaf node
				if ((set1.contains(root1)) || (root1.left == null && root1.right == null)) {
					result.push(root1);
					waitTree1 = false;
				} else {
					// put left child
					if (root1.left != null) {
						stack1.push(root1.left);
					}
					// put root
					stack1.push(root1);
					set1.add(root1);// mark root as visited
					// put right
					if (root1.right != null) {
						stack1.push(root1.right);
					}
				}
			}
			
			boolean waitTree2 = true;
			while(waitTree2) {
				// repeat for tree2
				TreeNode root2 = stack2.pop();
				// if already visited root or a leaf node
				if ((set2.contains(root2)) || (root2.left == null && root2.right == null)) {
					// match with result
					if (result.peek().data != root2.data) {
						System.out.println("They ain't matching!");
						return false;
					}
					waitTree2 = false;
				} else {
					// get left child
					if (root2.left != null) {
						stack2.push(root2.left);
					}
					stack2.push(root2);
					set2.add(root2);// mark root as visited
					if (root2.right != null) {
						stack2.push(root2.right);
					}
				}
			}
		}
		return true;
	}

// Test Code:

public static void testInOrderParallel() throws Exception {
//		smaller tree example...
//		TreeNode tree1 = new TreeNode(5);
//		tree1.left = new TreeNode(3);
//		tree1.right = new TreeNode(7);
//
//		TreeNode tree2 = new TreeNode(3);
//		tree2.right = new TreeNode(5);
//		tree2.right.right = new TreeNode(7);
//		Complex tree example...
		TreeNode tree1 = new TreeNode(6);
		tree1.left = new TreeNode(4);
		tree1.left.right = new TreeNode(5);
		tree1.right = new TreeNode(8);
		tree1.right.left = new TreeNode(7);
		
		TreeNode tree2 = new TreeNode(7);
		tree2.left = new TreeNode(5);
		tree2.left.left = new TreeNode(4);
		tree2.left.right = new TreeNode(6);
		tree2.right = new TreeNode(8);
		
		System.out.println(testInOrderStack(tree1, tree2));

	}

You could always do the in-order of one, flattening to, say, an array, then do the other, comparing with the in-order of the first. However this ends up reading an entire tree when they may differ right from the first node. So the better approach is to read the in-order of both at the same time and short-circuit out when you detect a difference.In-order traversal of trees can be done iteratively using stacks. A recursive solution is also possible and easier to code.

// Helper to push left most node rooted at n to stack
void pushLeftMostNode(Node n, Stack<Node> s) {
     while (n != null && n.left != null) {
        n = n.left;
        s.push(n);
    }
}

// Helper to push in-order next node rooted at n to stack
void pushInOrderNextNode(Node n, Stack<Node> s) {
    if (n.left != null) {
        pushLeftMostNode(n, s);
    } else if (n.right != null) {
        s.push(n.right);
        pushLeftMostNode(n.right, s);
    }
}

boolean isSame(Node n1, Node n2) {

    // Use stacks to iterate over trees in-order
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();

    // While stacks contain nodes, tops of stack will be the in-order next node
    while (!s1.isEmpty() && !s2.isEmpty() {
        n1 = s1.pop();
        n2 = s2.pop();
        if (n1.val != n2.val) {
            return false; // Short-circuit out
        }
        // Push in-order next nodes for trees rooted at n1 and n2
        pushInOrderNextNode(n1, s1);
        pushInOrderNextNode(n2, s2);
    }

    // If either stack contains nodes at this point, then trees are different sizes
    // Otherwise, trees are the same size and in-order traversals are the same too
    return !s1.isEmpty() || !s2.isEmpty();
}

If a 2 trees have the same in-order, then 1 tree will have the reverse postorder of the other's inorder. You can use a stack to push values for one tree. Then do a post order of 2nd tree, and keep popping till you don't see a match.

The problem becomes easy if you have an in-order tree iterator and this solution doesn't require you to traverse all the nodes of the tree.