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.

Additional information

• The number of nodes in both trees is in the range [0, 100].
• -10^4 <= Node.val <= 10^4

Example 1:

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

Output: true

Example 2:

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

Output: false

Explanation: The trees have the same values but different structures.

Example 3:

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

Output: false

Recursive Depth-First Search (DFS)

Intuition

Since binary trees are recursive data structures, comparing them recursively is the most natural approach. Two trees are the same if:

1. Their root nodes have the same value.
2. Their left subtrees are identical.
3. Their right subtrees are identical.

We can establish base cases to handle when we reach the leaves (null nodes).

Algorithm

1. Base Case 1: If both p and q are None, it means we have reached the end of identical branches. Return True.
2. Base Case 2: If either p or q is None (but not both), the structures differ. Return False.
3. Base Case 3: If the values of p and q are different, the trees are not identical. Return False.
4. Recursive Step: Recursively call the function on the left children and right children. Return True only if both recursive calls return True.

def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    # Both nodes are None (end of branch)
    if not p and not q:
        return True
    
    # One is None, or values don't match
    if not p or not q or p.val != q.val:
        return False
        
    # Recursively check left and right subtrees
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit each node in both trees exactly once, where n is the number of nodes in the smaller tree.

• Space complexity: O(h)

• Reason: The space complexity is determined by the recursion stack. In the worst case (a perfectly skewed tree), the height h equals n, leading to O(n) space. For a balanced tree, it is O(log n).

Iterative Breadth-First Search (BFS)

Intuition

If we want to avoid recursion, we can traverse both trees level by level simultaneously using a Queue. At each step, we extract a pair of nodes (one from p, one from q) and compare them.

Algorithm

1. Initialize a queue with a tuple containing the roots: (p, q).
2. While the queue is not empty:

• Pop the tuple (node_p, node_q).
• If both are None, continue to the next iteration (this branch matches so far).
• If one is None or their values differ, return False.
• Append their left children to the queue: (node_p.left, node_q.left).
• Append their right children to the queue: (node_p.right, node_q.right).

3. If the loop completes without returning False, the trees are identical. Return True.

from collections import deque

def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    queue = deque([(p, q)])
    
    while queue:
        node_p, node_q = queue.popleft()
        
        # Both are None, valid path
        if not node_p and not node_q:
            continue
            
        # One is None or values are different, invalid path
        if not node_p or not node_q or node_p.val != node_q.val:
            return False
            
        # Queue the children for structural comparison
        queue.append((node_p.left, node_q.left))
        queue.append((node_p.right, node_q.right))
        
    return True

Time & Space Complexity

• Time complexity: O(n)

• Reason: Each node is processed exactly once.

• Space complexity: O(n)

• Reason: In the worst case (a perfectly balanced tree), the queue will hold all the leaf nodes at the bottom level, which can be up to n/2 nodes.