Problem Statement

Given the roots of two binary trees, p and q, write a function to check if they are the same tree.

Two binary trees are considered the same if:

1. They are structurally identical, and
2. The nodes have the same value.

Example 1:

Input: 
p = [1,2,3], q = [1,2,3]
Output: true
Explanation: Both trees are identical in structure and values.

Example 2:

Input: 
p = [1,2], q = [1,null,2]
Output: false
Explanation: Tree structures differ.

Example 3:

Input: 
p = [1,2,1], q = [1,1,2]
Output: false
Explanation: Node values differ even though structure is same.

---

Intuition

We need to verify two conditions simultaneously at every node:

1. Both nodes exist (structure check).
2. Their values are equal (value check).

This is a classic recursive comparison problem — we can compare nodes top-down.

At any point:

• If both nodes are null → return true
• If only one is null → return false
• Otherwise:
  • Compare current node values.
  • Recursively compare left subtrees.
  • Recursively compare right subtrees.

If all checks pass, the trees are the same.

---

Recursive Approach (Depth-First Search)

Steps

1. If both p and q are null → return true.
2. If one of them is null → return false.
3. If p.val != q.val → return false.
4. Recursively check:
   • isSameTree(p.left, q.left)
   • isSameTree(p.right, q.right)
5. Return true only if both subtrees are same.

---

Java Solution

public 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);
    }
}

---

Complexity Analysis

• Time Complexity: O(n)
  We visit each node once in both trees, where n is the number of nodes.
• Space Complexity: O(h)
  Due to recursion stack, where h is the height of the tree (O(log n) for balanced, O(n) for skewed).

---

Iterative Approach (Using Queue or Stack)

Instead of recursion, we can use an iterative Breadth-First Search (BFS) or Depth-First Search (DFS).

Java Iterative BFS Example

import java.util.*;

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(p);
        queue.add(q);
        
        while (!queue.isEmpty()) {
            TreeNode first = queue.poll();
            TreeNode second = queue.poll();
            
            if (first == null && second == null) continue;
            if (first == null || second == null) return false;
            if (first.val != second.val) return false;
            
            queue.add(first.left);
            queue.add(second.left);
            queue.add(first.right);
            queue.add(second.right);
        }
        
        return true;
    }
}

This BFS-based approach avoids recursion and processes nodes in parallel.

---

Dry Run

Let’s take:

p = [1,2,3]
q = [1,2,3]

Tree structures:

Tree p:        Tree q:
    1              1
   / \            / \
  2   3          2   3

Step	Node p	Node q	Comparison	Result
1	1	1	equal → continue	✓
2	2	2	equal → continue	✓
3	3	3	equal → continue	✓
4	null	null	both null	✓

All recursive checks returned true → Final Output: true

---

Example of a Failing Case

p = [1,2], q = [1,null,2]

Trees:

Tree p:        Tree q:
    1              1
   /                \
  2                  2

Dry Run:

Step	Node p	Node q	Comparison	Result
1	1	1	equal	✓
2	2	null	one null → false	✗

Final Output → false

---

Key Takeaways

1. Recursion provides a clean and direct way to compare trees.
2. Always check null cases before accessing node values.
3. If both nodes exist and have the same value, recursively check both subtrees.
4. The iterative approach is useful to avoid recursion depth limits.