CareerCup

private static boolean isBstSame(BSTNode root1,BSTNode root2) {
		BSTNode temp1,temp2;
		Queue<BSTNode> q1 = new LinkedBlockingDeque<BSTNode>();
		Queue<BSTNode> q2 = new LinkedBlockingDeque<BSTNode>();
		if (root1 == null && root2==null)
			return true;
		q1.add(root1);
		q2.add(root2);
		while (!q1.isEmpty() && !q2.isEmpty()) {
			temp1 = q1.poll();
			temp2=q2.poll();
			
			if(temp1.getData()!=temp2.getData())
				return false;
			if (temp1.getLeft() != null)
				q1.add(temp1.getLeft());
			if (temp1.getRight() != null)
				q1.add(temp1.getRight());
			
			if (temp2.getLeft() != null)
				q2.add(temp2.getLeft());
			if (temp2.getRight() != null)
				q2.add(temp2.getRight());
		}
		return true;
	}

There is the same problem in Leetcode called same tree.
Just do a level order traversal.

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> firstQueue = new LinkedList<TreeNode>();
        Queue<TreeNode> secondQueue = new LinkedList<TreeNode>();
        firstQueue.add(p);
        secondQueue.add(q);
        while(!firstQueue.isEmpty() && !secondQueue.isEmpty()){
            TreeNode first = firstQueue.poll();
            TreeNode second = secondQueue.poll();
            if(first == null && second == null){
                continue;
            }else
                if(first == null || second == null){
                    return false;
                }
            else{
                if(first.val != second.val){
                    return false;
                }
                firstQueue.add(first.left);
                firstQueue.add(first.right);
                secondQueue.add(second.left);
                secondQueue.add(second.right);
            }
        }
        return true;
    }
}

Here my solution using queue, the idea like iterative dfs.

bool isSameTree (TreeNode * a, TreeNode * b) {
	if (a == NULL && b == NULL)
		return true;
	if (a == NULL || b == NULL) 
		return false;

	queue < TreeNode* > qa;
	queue < TreeNode* > qb;
	qa.push(a);
	qb.push(b);
	while (qa.size() != 0) {
		
		TreeNode * first = qa.front(); qa.pop();
		TreeNode * second = qb.front(); qb.pop();
		if (first -> val != second -> val)
			return false;

		if (first -> left && !second -> left)
			return false;

		if (!first -> left && second -> left)
			return false;

		if (first -> left) {
			qa.push(first -> left);
			qb.push(second -> left);
		}

		if (first -> right && !second -> right)
			return false;

		if (!first -> right && second -> right)
			return false;

		if (first -> right) {
			qa.push(first -> right);
			qb.push(second -> right);
		}
	}
	return true;

}

Can we use queue?

Use queue and poll each data and compare . If at any times , the value is unequal , the trees are not the same .

Same data and shape or same data?
For same shape and data the previous solutions are good enough.
But for different data i don't think so, Why?
because, All of you assume that the two tree have the same appearance order.
What if the two tree have the same data but they have different In-order, Pre-order and Pre-order, and yes that may happen since the question talks about Binary Trees not Binary Search Tree.