Same Tree

Given the roots p and q of two binary trees, return true if they are the same — identical in structure and with equal node values at every position — and false otherwise.

Each tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Two trees are the same when their roots are equal and both subtrees are pairwise the same.

Handle the null cases first: two nulls match, one null against a node does not.

Recurse on both trees at once, ANDing the left and right results.

Common doubts

If you read p.val when p is null you'll crash; the null checks must come first.

Both subtrees must match for the trees to be identical; OR would accept a mismatch on one side.

Yes — both null is the matching base case, returning true.

Interview follow-ups

· What an interviewer asks next.

Run this same-tree check at every node of the larger tree (LeetCode 572), or compare serialized forms.

Compare p.left with q.right and p.right with q.left instead — that's the symmetric-tree pattern.

Fun facts

Same-tree is the building block of subtree-of-another-tree: you just run it at every candidate root.
Swapping the recursion to cross the children (left-vs-right) turns this into the symmetric-tree check.

Asked at

AmazonMicrosoftApple

Frequently Sometimes Occasionally

Example 1

Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Same structure and same values at every position.

Example 2

Input: p = [1, 2], q = [1, null, 2]
Output: false
The 2 is a left child in p but a right child in q — different structure.

Example 3

Input: p = [1, 2, 1], q = [1, 1, 2]
Output: false
Same structure but the child values are swapped.

Constraints

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

Two trees are the same when their roots match and their left subtrees are the same and their right subtrees are the same. That's the recursion. The base cases handle nulls: two nulls match; one null against a real node does not.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary tree. Nodes with a value and up to two children (left, right).

Parallel recursion. Recursing over two trees at once, matching them position by position.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“What counts as 'same'?”

Identical shape and identical values at every corresponding position.

“Are two empty trees the same?”

Yes — both null is a match.

The ideal opening — say it like this

Two trees are the same if the roots have equal values and their left and right subtrees are pairwise the same.

I recurse over both trees together; the base cases are two nulls (equal) and one null versus a node (not equal).

Understand the problem

Worked example — p = [1, 2, 3], q = [1, 2, 3]

compare 1 vs 1  ✓ -> compare left (2 vs 2) and right (3 vs 3)
2 vs 2 ✓ (both children null) ; 3 vs 3 ✓
answer: true

Key observations

1Aha

Same = roots equal AND subtrees same

The recursion mirrors the definition exactly; the AND of the two subtree comparisons is the crux.

2Aha

Null bookkeeping is the base case

Two nulls → equal; one null and one node → structurally different, so not equal.

3Aha

Linear time, height space

Each corresponding node pair is compared once (O(n)); recursion depth is O(height).

Brute force vs optimal

	Iterative (queue of pairs)	Recursive
Idea	Compare node pairs from a queue in lockstep	roots equal AND left same AND right same
Time	O(n)	O(n)
Space	O(n)	O(height)

Both are O(n); the recursion is a direct transcription of the definition. Full code is in the Approaches selector below.

Summary

Key takeaway

Two trees are the same iff their roots are equal and both subtrees are pairwise the same. Handle the null base cases, then AND the recursive results. O(n) time, O(height) space.

same(p, q):
    if p is null and q is null: return true
    if p is null or q is null or p.val != q.val: return false
    return same(p.left, q.left) and same(p.right, q.right)