Same Tree (LC 100)

Pattern: DFS — Simultaneous Recursive Traversal Difficulty: Easy Key Concept: Two trees are identical iff their roots have equal values and their left subtrees are identical and their right subtrees are identical.

Problem Statement

Given the roots of two binary trees p and q, return true if they are structurally identical and the nodes have the same values.

Example

• p = [1,2,3], q = [1,2,3] → true
• p = [1,2], q = [1,null,2] → false
• p = [1,2,1], q = [1,1,2] → false

---

1. Algorithm & Pseudocode

Recursive DFS

isSame(p, q):
    if p == null and q == null: return true
    if p == null or  q == null: return false
    if p.val != q.val:           return false
    return isSame(p.left, q.left) and isSame(p.right, q.right)

Iterative BFS (Pair Queue)

queue both roots together; pop pairs; for each pair: same checks, enqueue children pairs

---

2. Step-by-Step Analysis

Base cases

• Both null → identical (empty trees).
• Exactly one null → structurally different.

Recursive case Compare current node values; recurse on left and right children simultaneously.

Why DFS is natural Tree equality is inherently recursive — the property holds for the pair iff it holds for both child pairs.

Why short-circuit && matters If isSame(p.left, q.left) is false, we skip the right recursion entirely.

ASCII Trace for p = 1(2)(3), q = 1(2)(3)

visit (1,1) ✓
  visit (2,2) ✓
    visit (null,null) ✓
    visit (null,null) ✓
  visit (3,3) ✓
    visit (null,null) ✓
    visit (null,null) ✓
return true

---

3. The Dry Run

p = 1→(2,1), q = 1→(1,2)

Step	Pair	Result	Reason
1	(1,1)	recur	values equal
2	(2,1) left pair	false	2 != 1
3	propagates up	false	overall

---

4. Java Solution

Recursive

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

Time: (O(n)) — visit each node once Space: (O(h)) — recursion depth = tree height

Iterative — Pair BFS

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Deque<TreeNode[]> stack = new ArrayDeque<>();
        stack.push(new TreeNode[]{p, q});
        while (!stack.isEmpty()) {
            TreeNode[] cur = stack.pop();
            TreeNode a = cur[0], b = cur[1];
            if (a == null && b == null) continue;
            if (a == null || b == null) return false;
            if (a.val != b.val) return false;
            stack.push(new TreeNode[]{a.left,  b.left});
            stack.push(new TreeNode[]{a.right, b.right});
        }
        return true;
    }
}

Time: (O(n)) Space: (O(h))

---

5. The “Java vs. Others” Edge

• Java’s short-circuit && ensures isSameTree(p.right, q.right) isn’t evaluated when left mismatch is found — same trick Python uses with and.
• The recursive version is idiomatic and accepted in interviews. Iterative is needed only if the tree is so skewed that recursion overflows (rare in practice).
• For the Subtree of Another Tree (LC 572) problem, this method is reused as a helper.

---

6. Complexity Summary

Approach	Time	Space	Notes
Recursive	(O(n))	(O(h))	h = height. Worst case h = n (skewed)
Iterative	(O(n))	(O(h))	Same complexity, explicit stack