Code link: https://leetcode.com/problems/same-tree/

1. Recursive solution:

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        }
        
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

2. Iterative solution
   We can also use BFS to do level order traversal, with the help of a queue.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(p);
        queue.add(q);
        
        while (!queue.isEmpty()) {
            TreeNode lNode = queue.remove();
            TreeNode rNode = queue.remove();
            if (lNode == null && rNode == null) {
                continue;
            } else if (lNode == null || rNode == null) {
                return false;
            } else if (lNode.val != rNode.val) {
                return false;
            }
            
            queue.add(lNode.left);
            queue.add(rNode.left);
            queue.add(lNode.right);
            queue.add(rNode.right);

        }
        
        return true;
    }
}

Similar problem:

• Symmetric tree. The BFS approach is quite similar. The minor difference is the order of adding nodes to the queue.