Binary tree - Are two trees the same

"""
Idea: Do a BFS where each entry in the queue is a pair of ndoes, return False if at any point the two nodes in the current entry don't have the same value.
"""


# Recursive solution:

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        elif not q or not p:
            return False
        elif p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and self.isSameTree(p.left, q.left)


# Iterative solution:

from collections import deque
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        queue = deque([(p, q)])
        while queue:
            p, q = queue.popleft()
            if (p and not q) or (q and not p):
                return False
            if p and q:
                if p.val != q.val:
                    return False
                queue.append((p.left, q.left))
                queue.append((p.right, q.right))

        return True