Solutions

# Iterative or recursive DFS, or BFS (deque)
# trees

# Recursive DFS - O(n) time, O(n) space (O(ln n) if it's balanced)
def same_tree(p: TreeNode, q: TreeNode) -> bool:
    if p and not q:
        return False
    if not p and q:
        return False

    if p.val != q.val:
        return False
    
    return same_tree(p.left, q.left) and same_tree(p.right, q.right)


# Iterative DFS - O(n) time, O(n) space
def same_tree(p: TreeNode, q: TreeNode) -> bool:
    stack = [(p, q)]

    while stack:
        n1, n2 = stack.pop()

        if not n1 and not n2:
            continue
        if not n1 and n2 or (n1.val != n2.val):
            return False

        stack.append((n1.left, n2.left))
        stack.append((n1.right, n2.right))
        
    return True


# Iterative BFS
from collections import deque

def same_tree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    q1 = deque([p])
    q2 = deque([q])

    while q1 and q2:
        for _ in range(len(q1)):
            nodeP = q1.popleft()
            nodeQ = q2.popleft()

            if nodeP is None and nodeQ is None:
                continue
            if nodeP is None or nodeQ is None or nodeP.val != nodeQ.val:
                return False

            q1.append(nodeP.left)
            q1.append(nodeP.right)
            q2.append(nodeQ.left)
            q2.append(nodeQ.right)

    return True