Same Tree (LC 100)

Pattern: DFS (Simultaneous traversal)
Difficulty: Easy
Key Concept: Two trees are the same only if roots match and both left pairs and right pairs match recursively.

Problem Statement

You are given the roots of two binary trees, p and q. Return true if they are structurally identical and every corresponding node has the same value. Otherwise return false.

Input: TreeNode p, TreeNode q (either may be null).
Output: boolean — true if both trees are the same, false otherwise.

Examples:

• p = [1,2,3], q = [1,2,3] → true.
• p = [1,2], q = [1,null,2] → false (different shape: in q, 2 is the right child of root, not the left).

---

1. Algorithm & Pseudocode

Brute force (serialize then compare)

serialize(root, list):
  if root is null:
    append sentinel (e.g. "null") to list and return
  append root.val to list
  serialize(root.left, list)
  serialize(root.right, list)

isSameTree(p, q):
  listP = empty list
  listQ = empty list
  serialize(p, listP)
  serialize(q, listQ)
  return listP equals listQ

Idea: Two trees are identical iff their preorder (or preorder + null markers) serializations match.

Optimal (simultaneous DFS)

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

Idea: At each step, check the current pair of nodes; only recurse if values match and nullity matches.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why compare p and q together?
   “Same tree” is a relationship between pairs of nodes at the same position. Walking both trees in lockstep avoids building full lists.

2. Why both null means true?
   Two empty subtrees match: there is no mismatch below that branch.

3. Why one null and one not means false?
   One side has a node where the other has nothing — structure differs.

4. Why p.val != q.val before recursing?
   If values differ at this position, subtrees do not matter; the answer is false.

5. == on int values in Java:
   LeetCode’s TreeNode usually stores int val. Comparing with == is correct. If val were Integer, use Objects.equals(p.val, q.val) to avoid NPE and reference equality bugs.

6. Short-circuit in one return:
   In Java, return cond1 && cond2 && cond3 evaluates left to right and stops on the first false. That avoids extra recursion once a mismatch is found.

---

3. The Dry Run

Case A — p = [1,2,3], q = [1,2,3]

    p           q
    1           1
   / \         / \
  2   3       2   3

Step	Call	p	q	Check	Result so far
1	isSame(1, 1)	node 1	node 1	vals equal	continue
2	isSame(2, 2)	node 2	node 2	vals equal	continue
3	isSame(null, null)	null	null	both null	true
4	isSame(null, null)	null	null	both null	true
5	Return from (2,2)	—	—	left ∧ right	true
6	isSame(3, 3)	node 3	node 3	vals equal	continue
7	isSame(null, null) ×2	null	null	both null	true
8	Return from (1,1)	—	—	full tree	true

Final: true.

Case B — p = [1,2], q = [1,null,2]

    p           q
    1           1
   /             \
  2               2

Step	Call	p	q	Check	Outcome
1	isSame(root_p, root_q)	1	1	values equal	recurse
2	isSame(p.left, q.left)	2	null	one null, one not	false

The expression isSame(left) && isSame(right) short-circuits: once the left call returns false, the right call is not evaluated.

Final: false (structures differ: left vs right child for 2).

---

4. Java Solution

Brute Force

Idea: Serialize both trees to lists with null markers, then compare lists.

Time: O(n) — visit every node in each tree.
Space: O(n) — two lists plus recursion/stack.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        List<String> listP = new ArrayList<>();
        List<String> listQ = new ArrayList<>();
        serialize(p, listP);
        serialize(q, listQ);
        return listP.equals(listQ);
    }

    private void serialize(TreeNode root, List<String> out) {
        if (root == null) {
            out.add("null");
            return;
        }
        out.add(String.valueOf(root.val));
        serialize(root.left, out);
        serialize(root.right, out);
    }
}

Optimal

Time: O(min(n, m)) — stop at first mismatch. 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) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Compact equivalent (same logic, relies on short-circuit):

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

---

5. The “Java vs. Others” Edge

• Null checks: Use == and != for reference equality on TreeNode; that is idiomatic Java.
• Primitive int: p.val == q.val is correct for LeetCode’s standard definition. For Integer, prefer Objects.equals(p.val, q.val).
• Short-circuit: a && b && c does not evaluate b or c after a false. That saves work when the left subtree already disagrees.
• Compared to Python: Python might write if not p and not q: return True; Java separates null checks explicitly.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n + m)	O(n + m)	n, m = nodes in each tree; two serializations + comparison
Optimal	O(min(n, m))	O(h)	Stops early on mismatch; h = min height along path

For balanced trees, h = O(log n); skewed trees h = O(n).