131. Same Tree
🔗 LeetCode Problem: 100. Same Tree
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, Recursion, DFS, BFS
Problem Statement
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Example 1:
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]
Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]
Output: false
Constraints:
- The number of nodes in both trees is in the range [0, 100]
- -10^4 <= Node.val <= 10^4
🌳 Visual Understanding - Drawing the Trees First!
Let's visualize what we're comparing.
Example 1: Same Trees ✓
Tree p: Tree q:
1 1
/ \ / \
2 3 2 3
Structurally identical? YES ✓
Same values? YES ✓
Result: true
Example 2: Different Structure ✗
Tree p: Tree q:
1 1
/ \
2 2
Structurally identical? NO ✗
p has left child, q has right child
Result: false
Example 3: Same Structure, Different Values ✗
Tree p: Tree q:
1 1
/ \ / \
2 1 1 2
Structurally identical? YES ✓
Same values? NO ✗
p.left = 2, q.left = 1 (different!)
p.right = 1, q.right = 2 (different!)
Result: false
Edge Cases to Consider:
Case 1: Both null
p = null q = null
Result: true (empty trees are the same)
Case 2: One null, one not
p = null q = 1
/
2
Result: false (different structure)
Case 3: Single node, same value
p = 5 q = 5
Result: true
Case 4: Single node, different value
p = 5 q = 3
Result: false
🧠 Recursive Thinking - The Foundation
The Key Question:
"When are two trees the same?"
Let's think recursively. A tree is defined recursively:
A tree is either:
1. Empty (null) - BASE CASE
2. A root node with left and right subtrees - RECURSIVE CASE
Breaking Down the Problem:
Two trees are the SAME if and only if:
1. Their ROOT nodes are the same (same value)
AND
2. Their LEFT subtrees are the same
AND
3. Their RIGHT subtrees are the same
This is PERFECT for recursion!
Identifying Base Cases:
Base Case 1: Both trees are null
isSameTree(null, null) → true
WHY? Two empty trees are identical
Base Case 2: One tree is null, other is not
isSameTree(null, node) → false
isSameTree(node, null) → false
WHY? Different structure
Base Case 3: Root values are different
isSameTree(p, q) where p.val ≠ q.val → false
WHY? Even if structure matches, values must match
The Recursive Case:
If we reach here, we know:
- Both nodes exist (not null)
- Both nodes have same value
Now check subtrees:
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
WHY?
- p.left and q.left must be same trees
- p.right and q.right must be same trees
- Both conditions must be true (AND)
🎯 Solution 1: Recursive DFS (Most Natural)
The Complete Recursive Solution
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Base Case 1: Both nodes are null
// WHY? Empty trees are considered identical
if (p == null && q == null) {
return true;
}
// Base Case 2: One node is null, the other is not
// WHY? Different structure means not the same tree
if (p == null || q == null) {
return false;
}
// Base Case 3: Node values are different
// WHY? Even if structure is same, values must match
if (p.val != q.val) {
return false;
}
// Recursive Case: Check both subtrees
// WHY? Current nodes match, now verify subtrees match
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
Understanding Each Line:
if (p == null && q == null) return true;
// Stopping condition: We've reached leaves (or both trees are empty)
// This is the "success" base case
if (p == null || q == null) return false;
// One is null, one isn't → structure differs
// This catches cases like:
// p: 1 q: 1
// / \
// 2 2
if (p.val != q.val) return false;
// Both exist but have different values
// This catches cases like:
// p: 1 q: 2
// / \ / \
// 2 3 2 3
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
// Trust recursion! If left subtrees match AND right subtrees match,
// then the whole tree matches
🔍 Detailed Dry Run with Recursion Visualization
Let's trace through Example 1 step by step.
Input Trees:
Tree p: Tree q:
1 1
/ \ / \
2 3 2 3
The Recursion Call Tree:
Legend:
→ means "calls"
← means "returns"
✓ means "true"
✗ means "false"
CALL STACK VISUALIZATION:
Level 0: isSameTree(p=1, q=1)
│
├─ p=1, q=1: Values match ✓
├─ p not null, q not null ✓
│
├─ RECURSE LEFT ─────────────────────────────────┐
│ │
│ Level 1: isSameTree(p=2, q=2) │
│ │ │
│ ├─ p=2, q=2: Values match ✓ │
│ ├─ p not null, q not null ✓ │
│ │ │
│ ├─ RECURSE LEFT ─────────────┐ │
│ │ │ │
│ │ Level 2: isSameTree(p=null, q=null) │
│ │ │ │ │
│ │ └─ Both null → return true ✓ │
│ │ │ │
│ │ ← returns true ✓ │ │
│ │ │
│ ├─ RECURSE RIGHT ────────────┐ │
│ │ │ │
│ │ Level 2: isSameTree(p=null, q=null) │
│ │ │ │ │
│ │ └─ Both null → return true ✓ │
│ │ │ │
│ │ ← returns true ✓ │ │
│ │ │
│ └─ true && true → return true ✓ │
│ │
│ ← returns true ✓ │
│ │
├─ RECURSE RIGHT ────────────────────────────────┐
│ │
│ Level 1: isSameTree(p=3, q=3) │
│ │ │
│ ├─ p=3, q=3: Values match ✓ │
│ ├─ p not null, q not null ✓ │
│ │ │
│ ├─ RECURSE LEFT ─────────────┐ │
│ │ │ │
│ │ Level 2: isSameTree(p=null, q=null) │
│ │ │ │ │
│ │ └─ Both null → return true ✓ │
│ │ │ │
│ │ ← returns true ✓ │ │
│ │ │
│ ├─ RECURSE RIGHT ────────────┐ │
│ │ │ │
│ │ Level 2: isSameTree(p=null, q=null) │
│ │ │ │ │
│ │ └─ Both null → return true ✓ │
│ │ │ │
│ │ ← returns true ✓ │ │
│ │ │
│ └─ true && true → return true ✓ │
│ │
│ ← returns true ✓ │
│ │
└─ true && true → return true ✓
FINAL RESULT: true ✓
Step-by-Step Trace (Tabular Format):
Call# | p.val | q.val | p==null | q==null | Action | Returns
-------|---------|---------|---------|---------|---------------------------|--------
1 | 1 | 1 | No | No | Check value: 1==1 ✓ | ?
2 | 2 | 2 | No | No | Check left: 2==2 ✓ | ?
3 | null | null | Yes | Yes | Both null | true
4 | null | null | Yes | Yes | Both null | true
| | | | | Call 2 returns: T && T | true
5 | 3 | 3 | No | No | Check right: 3==3 ✓ | ?
6 | null | null | Yes | Yes | Both null | true
7 | null | null | Yes | Yes | Both null | true
| | | | | Call 5 returns: T && T | true
| | | | | Call 1 returns: T && T | true
FINAL: true
What Each Node "Sees" and "Returns":
Node p=1 asks:
"Is my left subtree (2) same as q's left (2)?"
→ Delegates to recursive call
→ Gets back: true ✓
"Is my right subtree (3) same as q's right (3)?"
→ Delegates to recursive call
→ Gets back: true ✓
"Both my subtrees match!"
→ Returns: true ✓
Node p=2 asks:
"Is my left subtree (null) same as q's left (null)?"
→ Gets back: true ✓
"Is my right subtree (null) same as q's right (null)?"
→ Gets back: true ✓
"Both match!"
→ Returns: true ✓
Node p=3: (same logic as p=2)
→ Returns: true ✓
📊 Example 2 Dry Run - Different Structure
Input Trees:
Tree p: Tree q:
1 1
/ \
2 2
Recursion Flow:
Call 1: isSameTree(p=1, q=1)
│
├─ p=1, q=1: Values match ✓
├─ p not null, q not null ✓
│
├─ RECURSE LEFT ─────────────────────┐
│ │
│ Call 2: isSameTree(p=2, q=null) │
│ │ │
│ ├─ p=2, q=null │
│ ├─ One is null, one is not │
│ └─ return false ✗ │
│ │
│ ← returns false ✗ │
│ │
├─ Left returned false │
├─ No need to check right (AND short-circuits)
│
└─ return false ✗
FINAL RESULT: false ✗
WHY IT FAILS:
- At node 1, left subtrees don't match
- p has left child (2), q has null
- Different structure → not same tree
🎯 Solution 2: Iterative DFS (Using Stack)
While recursion is natural for trees, we can also solve iteratively!
The Idea:
Instead of relying on the call stack (recursion),
we use our OWN stack to track pairs of nodes to compare.
Process:
1. Push initial pair (p, q) onto stack
2. While stack not empty:
a. Pop a pair
b. Check if they're the same (same checks as recursive)
c. If same, push their children pairs onto stack
3. If we process all pairs successfully → true
Implementation:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Use a stack to store pairs of nodes to compare
Stack<TreeNode[]> stack = new Stack<>();
stack.push(new TreeNode[]{p, q});
while (!stack.isEmpty()) {
TreeNode[] pair = stack.pop();
TreeNode node1 = pair[0];
TreeNode node2 = pair[1];
// Both null - continue to next pair
if (node1 == null && node2 == null) {
continue;
}
// One null, one not - trees differ
if (node1 == null || node2 == null) {
return false;
}
// Different values - trees differ
if (node1.val != node2.val) {
return false;
}
// Push children pairs for comparison
// Order doesn't matter, but be consistent
stack.push(new TreeNode[]{node1.left, node2.left});
stack.push(new TreeNode[]{node1.right, node2.right});
}
// All pairs matched
return true;
}
}
Dry Run - Iterative Approach:
Trees:
Tree p: Tree q:
1 1
/ \ / \
2 3 2 3
Stack Operations:
Initial: stack = [(p=1, q=1)]
Iteration 1:
Pop: (1, 1)
Check: Both not null, values match (1 == 1) ✓
Push: (p.left=2, q.left=2), (p.right=3, q.right=3)
stack = [(2,2), (3,3)]
Iteration 2:
Pop: (3, 3)
Check: Both not null, values match (3 == 3) ✓
Push: (null, null), (null, null)
stack = [(2,2), (null,null), (null,null)]
Iteration 3:
Pop: (null, null)
Check: Both null, continue ✓
stack = [(2,2), (null,null)]
Iteration 4:
Pop: (null, null)
Check: Both null, continue ✓
stack = [(2,2)]
Iteration 5:
Pop: (2, 2)
Check: Both not null, values match (2 == 2) ✓
Push: (null, null), (null, null)
stack = [(null,null), (null,null)]
Iteration 6:
Pop: (null, null)
Check: Both null, continue ✓
stack = [(null,null)]
Iteration 7:
Pop: (null, null)
Check: Both null, continue ✓
stack = []
Stack empty → return true ✓
🎯 Solution 3: BFS (Level Order Traversal)
We can also use BFS with a queue!
The Idea:
Process trees level by level
Use a queue to store pairs of nodes at same level
Implementation:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Use a queue for BFS
Queue<TreeNode[]> queue = new LinkedList<>();
queue.offer(new TreeNode[]{p, q});
while (!queue.isEmpty()) {
TreeNode[] pair = queue.poll();
TreeNode node1 = pair[0];
TreeNode node2 = pair[1];
// Both null - continue
if (node1 == null && node2 == null) {
continue;
}
// One null, one not - different
if (node1 == null || node2 == null) {
return false;
}
// Different values - different
if (node1.val != node2.val) {
return false;
}
// Enqueue children pairs
queue.offer(new TreeNode[]{node1.left, node2.left});
queue.offer(new TreeNode[]{node1.right, node2.right});
}
return true;
}
}
BFS vs DFS - Which to Use?
DFS (Recursive):
✓ Most natural for trees
✓ Cleaner, shorter code
✓ Easier to understand
✗ Uses call stack (stack overflow risk for very deep trees)
DFS (Iterative):
✓ Avoids recursion stack overflow
✓ Same memory usage as recursive in practice
✗ Slightly more code
BFS (Queue):
✓ Level-by-level comparison
✓ Finds differences faster if they're near the root
✗ More memory for wide trees
✗ Slightly more complex
For this problem: All three work equally well!
Personal preference: Recursive DFS (cleanest code)
📊 Complexity Analysis
Recursive DFS Solution:
Time Complexity: O(min(n, m))
Where:
n = number of nodes in tree p
m = number of nodes in tree q
Why min(n, m)?
- We visit each node once
- We stop early if trees differ
- Worst case: both trees are identical
→ Visit all n nodes (assuming n ≤ m)
Example:
Tree p: 100 nodes
Tree q: 1000 nodes
If they differ at node 10:
→ Only visit 10 nodes, not 100 or 1000!
Space Complexity: O(min(h_p, h_q))
Where:
h_p = height of tree p
h_q = height of tree q
Why?
- Recursion uses call stack
- Maximum depth = tree height
- We return early if trees differ
Best case: O(log n) - balanced tree
Worst case: O(n) - completely skewed tree
Example:
Balanced tree height = log(100) ≈ 7
→ Stack depth ≈ 7
Skewed tree height = 100
→ Stack depth = 100
Iterative Solutions:
Time Complexity: O(min(n, m)) - Same as recursive
Space Complexity: O(min(n, m))
Why potentially more than recursive?
- Stack/Queue can hold multiple nodes per level
- Worst case: completely balanced tree
→ Bottom level has n/2 nodes
→ Queue holds n/2 pairs
→ O(n) space
vs Recursive:
- Call stack only holds ONE path at a time
- Max depth = height = O(log n) for balanced tree
Trade-off:
Recursive: Better space for balanced trees
Iterative: Avoids stack overflow for deep trees
⚠️ Common Mistakes with Trees
Mistake 1: Forgetting to Check for Null
// ❌ WRONG - NullPointerException!
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p.val != q.val) { // Crashes if p or q is null!
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
// ✓ CORRECT - Check null first
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true; // Handle null first!
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);
}
Mistake 2: Wrong Base Case Order
// ❌ WRONG - Logic error
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) { // Checked first
return false; // Wrong! Both null should return true
}
if (p == null && q == null) return true; // Never reached!
// ...
}
// ✓ CORRECT - Right order
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true; // Both null first
if (p == null || q == null) return false; // One null second
// ...
}
Mistake 3: Not Understanding AND Logic
// ❌ WRONG - Only checks left OR right
return isSameTree(p.left, q.left) || isSameTree(p.right, q.right);
// This returns true if EITHER subtree matches!
// ✓ CORRECT - Must check BOTH
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
// Both subtrees must match
Mistake 4: Comparing References Instead of Values
// ❌ WRONG - Compares object references
if (p != q) return false;
// This checks if p and q point to the SAME object in memory!
// ✓ CORRECT - Compare values
if (p.val != q.val) return false;
// This checks if the VALUES are different
Mistake 5: Forgetting to Check Structure
// ❌ WRONG - Only checks values, not structure
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p.val == q.val) return true; // Wrong! Structure might differ
// ...
}
// ✓ CORRECT - Check both values AND structure
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false; // Structure check
if (p.val != q.val) return false; // Value check
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
🎯 Pattern Recognition - Similar Problems
This problem teaches the fundamental tree comparison pattern!
Core Pattern: Tree Comparison
Template:
1. Handle null cases (both null, one null)
2. Check current nodes (values, properties)
3. Recursively check subtrees
4. Combine results (AND/OR logic)
Related Problems:
1. Symmetric Tree (Problem 132)
Instead of comparing p and q:
Compare p.left with p.right (mirror image)
Same pattern, different comparison!
2. Subtree of Another Tree (Problem 138)
Check if tree s is identical to any subtree of tree t
Uses isSameTree as a helper!
Pattern: Tree matching
3. Merge Two Binary Trees
Combine two trees node by node
Similar structure:
- Handle null cases
- Process current nodes
- Recurse on subtrees
4. Invert Binary Tree (Problem 136)
Swap left and right subtrees
Pattern: Tree transformation with recursion
When to Use This Pattern:
✓ Comparing two trees (structure/values)
✓ Tree symmetry problems
✓ Tree matching/searching
✓ Tree transformation with comparison
📝 Quick Revision Notes
🎯 Core Concept
Compare two binary trees for structural identity and value equality. Use recursion naturally: check current nodes, then recurse on subtrees. Three base cases: (1) both null → true, (2) one null → false, (3) values differ → false. Recursive case: both subtrees must match.
⚡ Quick Implementation
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
}
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// // Approach 1 - Recursive DFS.
// return recursiveDFS(p, q);
// // Approach 2 - Iterative DFS using Stack.
// return iterativeDFS(p, q);
// Approach 3 - Iterative BFS using queue.
return iterativeBFS(p, q);
}
private boolean iterativeBFS(TreeNode p, TreeNode q) {
Queue<TreeNode[]> queue = new LinkedList<>();
queue.offer(new TreeNode[] {p, q});
while (!queue.isEmpty()) {
TreeNode[] polled = queue.poll();
TreeNode pp = polled[0];
TreeNode qq = polled[1];
// case 1 - check for next element on the stack.
if(pp == null && qq == null) {
continue;
}
// case 2 - only 1 reached
if(pp == null || qq == null) {
return false;
}
// normal check at the current node
if(pp.val != qq.val) {
return false;
}
// Push the children of current nodes to the stack for next comparison.
queue.offer(new TreeNode[] {pp.left, qq.left});
queue.offer(new TreeNode[] {pp.right, qq.right});
}
return true;
}
private boolean iterativeDFS(TreeNode p, TreeNode q) {
Stack<TreeNode[]> stack = new Stack<>();
stack.push(new TreeNode[] {p, q}); // roots are pushed
while (!stack.isEmpty()) {
TreeNode[] popped = stack.pop();
TreeNode pp = popped[0];
TreeNode qq = popped[1];
// case 1 - check for next element on the stack.
if(pp == null && qq == null) {
continue;
}
// case 2 - only 1 reached
if(pp == null || qq == null) {
return false;
}
// normal check at the current node
if(pp.val != qq.val) {
return false;
}
// Push the children of current nodes to the stack for next comparison.
stack.push(new TreeNode[] {pp.left, qq.left});
stack.push(new TreeNode[] {pp.right, qq.right});
}
return true;
}
private boolean recursiveDFS(TreeNode p, TreeNode q) {
// base case 1 - reached leaf nodes.
if(p == null && q == null) {
return true;
}
// base case 2 - only 1 reached
if(p == null || q == null) {
return false;
}
// normal check at the current node
if(p.val != q.val) {
return false;
}
// check child nodes now.
return recursiveDFS(p.left, q.left) && recursiveDFS(p.right, q.right);
}
public static void main(String[] args) {
Solution s = new Solution();
TreeNode p1 = TreeNode.buildTree(new Integer[] {1, 2, 3});
TreeNode q1 = TreeNode.buildTree(new Integer[] {1, 2, 3});
System.out.println(s.isSameTree(p1, q1));
TreeNode p2 = TreeNode.buildTree(new Integer[] {1, 2});
TreeNode q2 = TreeNode.buildTree(new Integer[] {1,null,2});
System.out.println(s.isSameTree(p2, q2));
TreeNode p3 = TreeNode.buildTree(new Integer[] {1,2,1});
TreeNode q3 = TreeNode.buildTree(new Integer[] {1,1,2});
System.out.println(s.isSameTree(p3, q3));
}
}
🔑 Key Insights
Recursion for Trees:
Trees are DEFINED recursively:
Tree = null OR (root + left subtree + right subtree)
Therefore, recursion is the NATURAL approach!
Base Cases First:
Always check null cases BEFORE accessing properties
Order matters:
1. Both null (success case)
2. One null (failure case)
3. Value check
4. Recursive case
AND Logic:
Both subtrees must match:
left matches && right matches
Not OR:
Would mean "at least one matches" - wrong!
Early Return:
Recursion stops early when mismatch found
No need to check all nodes if difference appears
Optimization happens automatically!
🎪 Memory Aid
"Check null, check value, check both sides"
"Both must match, not just one"
"Trust recursion, it works!" ✨
⚠️ Don't Forget
- Check null FIRST (before p.val or q.val)
- Both null returns TRUE (not false!)
- Use AND (&&) not OR (||) for subtrees
- Compare VALUES (p.val != q.val) not references (p != q)
- Base cases matter - order them correctly!
- Early return on mismatch (automatic with recursion)
🔗 Pattern for Future Problems
Tree Comparison Template:
1. if (both null) → true/success
2. if (one null) → false/failure
3. if (values differ) → false/failure
4. return recurse(left) && recurse(right)
This pattern appears in:
- Same Tree
- Symmetric Tree
- Subtree matching
- Tree equality checks
🎉 Congratulations!
You've mastered your first tree problem with recursion!
What You Learned:
✅ Visual tree thinking - Drawing trees first
✅ Recursive base cases - When to stop
✅ Recursive cases - What to do at each node
✅ Call stack visualization - How recursion flows
✅ Multiple approaches - Recursive DFS, Iterative DFS, BFS
✅ Complexity analysis - With recursion trees
✅ Common mistakes - And how to avoid them
✅ Pattern recognition - For similar problems
Next Steps:
This is your foundation for all tree problems!
Every tree problem uses similar concepts: - Base cases (null handling) - Recursive thinking - Subtree processing - Return value design
Practice next: Problem 132 - Symmetric Tree (uses same pattern!)
Happy tree climbing! 🌳🚀✨