LeetCode · #100

Same Tree Solution

Given two binary trees, check if they are structurally identical and have the same node values.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #100

🏗️

Pattern

Recursion — parallel traversal

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two trees are the same if they are structurally identical and the nodes have the same values.

Example
Input: p = [1,2,3], q = [1,2,3] Output: true
Constraints
• 0 ≤ number of nodes ≤ 100 • -10⁴ ≤ Node.val ≤ 10⁴
02
Section Two · Approach 1

Serialize & Compare — O(n)

Serialize both trees to strings (preorder with null markers) and compare strings. Works but allocates O(n) string space unnecessarily.

03
Section Three · Approach 2

Recursive Comparison — O(n)

Compare nodes in parallel: (1) both null → true, (2) one null → false, (3) values differ → false, (4) recurse on left and right children.

💡 Mental model: Two people walk through two houses simultaneously. At each room they check: "Same room exists? Same furniture?" If any mismatch, stop. If both reach dead ends at the same time → identical layout.
🎯 Building block: isSameTree is used as a helper in LC 572 (Subtree of Another Tree) — check it at every node of the main tree.
04
Section Four · Trace

Visual Walkthrough

Parallel comparison — p=[1,2,3] vs q=[1,2,3]
TREE p 1 2 3 == TREE q 1 2 3 PARALLEL COMPARISON ① Roots: p.val=1 == q.val=1 → ✓ match. Recurse left & right. ② Left: p.left=2 == q.left=2 → ✓ match. Both children null → true. ③ Right: p.right=3 == q.right=3 → ✓ match. Both children null → true. Answer: true ✓
05
Section Five · Implementation

Code — Java & Python

Java — 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); } }
Python — Recursive
class Solution: def isSameTree(self, p, q) -> bool: if not p and not q: return True if not p or not q: return False return (p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))
06
Section Six · Analysis

Complexity Analysis

ApproachTimeSpace
RecursiveO(n)O(h) — stack depth
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

CaseInputWhy It Matters
Both emptynull, nullSame → true.
One empty[1], nullDifferent structure → false.
Same structure, different values[1,2], [1,3]Values mismatch at p.left vs q.left → false.

← Back to Trees problems