Same Tree

Problem

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

Example 3:

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

Constraints:

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

Solution

Approach: Recursive DFS

The key insight is that two trees are the same if their roots have the same value and their left and right subtrees are also the same.

Implementation

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Both nodes are None
        if not p and not q:
            return True

        # One node is None, the other isn't
        if not p or not q:
            return False

        # Values don't match
        if p.val != q.val:
            return False

        # Check if left and right subtrees are the same
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Concise Version:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Complexity Analysis

Time Complexity: O(min(m, n)), where m and n are the numbers of nodes in the two trees. We stop as soon as we find a mismatch.
Space Complexity: O(min(h₁, h₂)), where h₁ and h₂ are the heights of the two trees (recursion stack).

Key Insights

Three Conditions: Trees are the same if: (1) both nodes are None, OR (2) both nodes exist with same values AND (3) their subtrees are the same.
Early Termination: We can return false immediately when we find any mismatch in structure or values.
Symmetric Recursion: We recursively compare left subtrees with left subtrees and right subtrees with right subtrees.
Base Cases: Both None (same), one None (different), or values differ (different).
Short-Circuit Evaluation: Using and operator ensures we only check right subtree if left subtrees match.