"""
Q100
Same Tree
Easy

Given two binary trees, write a function to check if they are
the same or not.

Two binary trees are considered the same if they are structurally
identical and the nodes have the same value.


"""


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:

        # iterative
        # BFS

        def compare(n1, n2):
            if not n1 and not n2:
                return True
            elif not n1 or not n2:
                return False
            else:
                return n1.val == n2.val

        from collections import deque
        queue = deque([(p, q)])
        while queue:
            curr_p, curr_q = queue.popleft()
            if not compare(curr_p, curr_q):
                return False
            elif curr_p:
                queue.append((curr_p.left, curr_q.left))
                queue.append((curr_p.right, curr_q.right))

        return True


a1 = TreeNode(1)
a2 = TreeNode(2)
a3 = TreeNode(1)

a1.left = a2
a1.right = a3

b1 = TreeNode(1)
b2 = TreeNode(2)
b3 = TreeNode(1)

b1.left = b2
b1.right = b3

sol = Solution()
print(sol.isSameTree(a1, b1))
"""
Q100
Same Tree
Easy

Given two binary trees, write a function to check if they are
the same or not.

Two binary trees are considered the same if they are structurally
identical and the nodes have the same value.


"""


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:

        # iterative
        # BFS

        def compare(n1, n2):
            if not n1 and not n2:
                return True
            elif not n1 or not n2:
                return False
            else:
                return n1.val == n2.val

        from collections import deque
        queue = deque([(p, q)])
        while queue:
            curr_p, curr_q = queue.popleft()
            if not compare(curr_p, curr_q):
                return False
            elif curr_p:
                queue.append((curr_p.left, curr_q.left))
                queue.append((curr_p.right, curr_q.right))

        return True


a1 = TreeNode(1)
a2 = TreeNode(2)
a3 = TreeNode(1)

a1.left = a2
a1.right = a3

b1 = TreeNode(1)
b2 = TreeNode(2)
b3 = TreeNode(1)

b1.left = b2
b1.right = b3

sol = Solution()
print(sol.isSameTree(a1, b1))
Q100 Same Tree Easy  Given two binary trees, write a function to check if they are the same or not.  Two binary trees are considered the same if they are structurally identical and the nodes have the same value. # Definition for a binary tree node. # iterative # BFS