Problem Statement

Given the roots of two binary trees p and q, 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.

Link To the Problem

Intuition

When comparing two binary trees, the key is to check structure and values at the same time.

• If both nodes are None, they are identical in that position.
• If one node is None but the other isn’t, the trees differ.
• If both nodes exist, their values must be equal, and their left and right subtrees must also be the same.

Approach

We perform a recursive check:

1. Base case 1: If both nodes are None, return True.

2. Base case 2: If only one of them is None, return False.

3. Base case 3: If the values don’t match, return False.

4. Recursive step: Check if both left subtrees and right subtrees are identical.

This ensures both the structure and values of the trees are the same.

Complexity

• Time complexity: Each node is visited exactly once, so the complexity is O(n) where n is the number of nodes (minimum of the two trees).

• Space complexity: The recursion depth depends on the height of the tree. In the worst case (skewed tree), the depth is O(n). In the best case (balanced tree), it’s O(log n). So, space complexity is O(h) where h is the height of the tree.

Code

# 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
class Solution:
    def is_same_tree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

        if p is None and q is None :
            return True

        if p is None or q is None :
            return False

        if p.val != q.val :
            return False

        return self.is_same_tree(p.left,q.left) and self.is_same_tree(p.right,q.right)