Same Binary Tree

Problem Statement

Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.

Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.

Example 1:

Input: p = [1,2,3], q = [1,2,3]


Output: true

Example 2:

Input: p = [4,7], q = [4,null,7]


Output: false

Example 3:

Input: p = [1,2,3], q = [1,3,2]


Output: false

Constraints:

  • 0 <= The number of nodes in both trees <= 100.
  • -100 <= Node.val <= 100

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Hint 1

Can you think of an algorithm that is used to traverse the tree? Maybe in terms of recursion.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse the tree. Can you think of a way to simultaneously traverse both the trees?

Hint 3

We traverse both trees starting from their root nodes. At each step in the recursion, we check if the current nodes in both trees are either null or have the same value. If one node is null while the other is not, or if their values differ, we return false. If the values match, we recursively check their left and right subtrees. If any recursive call returns false, the result for the current recursive call is false.

Solution

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


def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q:
        return True
    if p and q and p.val == q.val:
        return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
    else:
        return False

Time complexity: O(n) Space complexity: O(n)

Iterative DFS

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


def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    stack = [(p, q)]


    while stack:
        node1, node2 = stack.pop()


        if not node1 and not node2:
            continue
        if not node1 or not node2 or node1.val != node2.val:
            return False


        stack.append((node1.right, node2.right))
        stack.append((node1.left, node2.left))


    return True

Time complexity: O(n) Space complexity: O(n)

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


from collections import deque


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


    while q1 and q2:
        for _ in range(len(q1)):
            node_p = q1.popleft()
            node_q = q2.popleft()


            if node_p is None and node_q is None:
                continue
            if node_p is None or node_q is None or node_p.val != node_q.val:
                return False


            q1.append(node_p.left)
            q1.append(node_p.right)
            q2.append(node_q.left)
            q2.append(node_q.right)


    return True

Time complexity: O(n) Space complexity: O(n)