Problem #100: Same Tree

Intuition & Strategy Breakdown

Recursively compare two binary trees: check if current nodes are both null, or have equal values and identical left and right subtrees.

Python Solution

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # If both nodes are null, trees are same
        if not p and not q:
            return True
        
        # If one is null or values mismatch, trees are different
        if not p or not q or p.val != q.val:
            return False
        
        # Check left and right subtrees
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Java Solution

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // If both are null, they are the same
        if (p == null && q == null) return true;
        
        // If one is null or values don't match, they are different
        if (p == null || q == null || p.val != q.val) return false;
        
        // Recursively check left and right subtrees
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}