90. Same Tree

Walk both trees in lockstep. At each pair of positions: both empty is a match; one empty (but not the other) or differing values is a mismatch; otherwise recurse on the left pair and the right pair together.

Idea

Two trees are identical when every corresponding pair of nodes agrees in both structure and value. Recurse through both trees simultaneously, comparing the two current nodes and then their children pairwise.

Algorithm

isSameTree(p, q):

1. If both p and q are null → true (both ended together).
2. If exactly one is null, or p.val != q.val → false.
3. Otherwise return isSameTree(p.left, q.left) and isSameTree(p.right, q.right).

Worked example: p = [1,2,3], q = [1,2,3]

• Roots 1 == 1 ✓. Left 2 == 2 ✓ (leaves). Right 3 == 3 ✓ (leaves). All pairs match → true.

Contrast [1,2] vs [1,null,2]: at the root's children one side has a left child and the other a right child → structural mismatch → false.

Complexity

• Time: O(n) — visits each node pair once.
• Space: O(h) recursion depth.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}