Same Tree easy

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.

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

Steps

1. Base Case: If both p and q are None (empty trees), they are the same, return True.
2. Check for structural mismatch: If one of p or q is None but the other is not, they are not the same, return False.
3. Check node values: If the values of the root nodes (p.val and q.val) are different, return False.
4. Recursive calls: Recursively check if the left subtrees are the same and the right subtrees are the same using the function itself. Return True only if both recursive calls return True.

Explanation

The solution employs a recursive approach. It systematically compares the nodes of the two trees level by level. The base case handles the scenario where both trees are empty. The structural mismatch check ensures that trees with different structures are immediately identified as different. The recursive calls efficiently traverse the trees, comparing values at each corresponding node. The final result is a boolean indicating whether the trees are identical.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSameTree(p, q):
    """
    Checks if two binary trees are the same.

    Args:
        p: The root of the first binary tree.
        q: The root of the second binary tree.

    Returns:
        True if the trees are the same, False otherwise.
    """
    if p is None and q is None:
        return True  # Base case: both trees are empty
    if p is None or q is None:
        return False  # Structural mismatch
    if p.val != q.val:
        return False  # Node values differ

    # Recursively check left and right subtrees
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we visit each node once.
• Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), the height can be equal to N, resulting in O(N) space complexity. In the best case (a balanced tree), the height is log(N), resulting in O(log N) space complexity.