[Easy] 100. Same Tree

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.

Thinking Process

1. Three Base Cases: Both null, one null, or value mismatch

• Trees have no cycles — recursion is natural.
• Combine results from left and right subtrees at each node.
• Base case is usually null; height drives stack space.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Examples

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

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

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

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

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

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

Constraints

• The number of nodes in both trees is in the range [0, 100].
• -10^4 <= Node.val <= 10^4

Common Mistakes

1. Both empty: p = [], q = [] → return true
2. One empty: p = [], q = [1] → return false
3. Single node match: p = [1], q = [1] → return true
4. Single node mismatch: p = [1], q = [2] → return false
5. Same structure, different values: p = [1,2], q = [1,3] → return false

6. Different structure: p = [1,2], q = [1,null,2] → return false

7. Not checking both nulls first: Accessing values before null check

   # WRONG:
   if (p.val != q.val) return False; # ❌ Crashes if p or q is null
   

8. Wrong logic operator: Using OR instead of AND

   # WRONG:
   return isSameTree(p.left, q.left)  or  isSameTree(p.right, q.right);
   # ❌ Returns True if only one subtree matches
   

9. Not handling null correctly: Forgetting that one tree can be null while the other isn’t
10. Comparing references: Comparing node pointers instead of values
11. Missing value check: Only checking structure, not values

Related Problems

• LC 100: Same Tree - This problem
• LC 101: Symmetric Tree - Check if tree is symmetric
• LC 226: Invert Binary Tree - Mirror a binary tree
• LC 572: Subtree of Another Tree - Check if subtree exists
• LC 104: Maximum Depth of Binary Tree - Find maximum depth
• LC 110: Balanced Binary Tree - Check if tree is balanced

Key Takeaways

1. Three Base Cases: Both null, one null, or value mismatch
2. Symmetric Comparison: Compare corresponding nodes in both trees
3. AND Logic: Both subtrees must match for trees to be identical
4. Early Termination: Return false immediately when mismatch found
5. Pre-order Traversal: Check current node before recursing

References

• LC 100: Same Tree on LeetCode
• LeetCode Discuss — LC 100: Same Tree
• LeetCode Editorial (may require premium)

Template Reference

• Trees