Algorithm

Same Tree

Trees Pattern

Same Tree

Given the roots of two binary trees p and q, return true if they are identical: the same shape and the same value at every corresponding position. Two empty trees are identical. A tree is not identical to one that merely holds the same values in a different arrangement.

CONSTRAINTS
  • The number of nodes in each tree is in the range [0, 100]
  • -10⁴ <= Node.val <= 10⁴
  • Both structure and values must match
  • Either tree may be empty
EXAMPLE 1
Input: p = [1,2,3], q = [1,2,3]
Output: true
Same shape, same values in the same positions.
EXAMPLE 2
Input: p = [1,2], q = [1,null,2]
Output: false
Both trees hold the values 1 and 2, but in one the 2 is a left child and in the other a right child. Shape is part of identity, so this fails.
EXAMPLE 3
Input: p = [1,2,1], q = [1,1,2]
Output: false
Identical shapes and identical multisets of values, yet the values sit in swapped positions. Comparing sorted contents would wrongly pass this.
EXAMPLE 4
Input: p = [], q = []
Output: true
Two empty trees are the same tree. This is the base case the recursion rests on, not an exceptional input.
Does 'same' mean same values, same shape, or both?
Both, at every position. Two trees with the same values arranged differently are not the same.
What if both trees are empty?
True. And if exactly one is empty, false — that asymmetry is what the null checks encode.
Can I compare their traversals instead?
Only if the traversal includes null markers. A bare pre-order list is ambiguous about shape, as Serialize and Deserialize shows; with markers, comparing the two encodings does work, at the cost of building both strings.
Are the trees guaranteed to be the same size?
No. Different sizes are simply one way of being different, and the recursion detects it the moment one side runs out before the other.

Two trees are "the same" when they have the exact same shape and the same value at every matching spot. The trick: don't walk one tree — walk both at once, one foot in each, always standing on the same position in both.

text
   p:   1            q:   1
       / \               / \
      2   3             2   3     step through both together, same turns
Standing on a pair of nodes

At every step you're standing on a pair — a from tree p, b from tree q, at matching positions. Four things can happen:

- Both null → both trees stopped here the same way → this spot is fine, return true.
- Exactly one null → one has a node, the other doesn't → shapes differ, nothing below can fix it → false.
- Both exist, values differ → contents differ → false.
- Both exist and match → this spot's fine, but that says nothing about below. Same only if the left pair agrees AND the right pair agrees — two smaller copies of the same question.
text
   p:   1            q:   1
       /                   \
      2                     2       p's 2 is a LEFT child, q's is a RIGHT child
                                    left pair = (2, null) -> one null -> FALSE
python
def isSame(p, q):
    if p is None and q is None:
        return True                      # both stop here, same way
    if p is None or q is None:
        return False                     # one stops, one doesn't — shape differs
    if p.val != q.val:
        return False                     # value differs
    return isSame(p.left, q.left) and isSame(p.right, q.right)
Crucial Notecheck both-null before either-null. The p is None or q is None line is also true when both are null, so if it ran first it would wrongly return false for two empty spots. In this order, reaching line 3 guarantees both nodes exist, so p.val is safe to read. The and also short-circuits: the moment the left pair disagrees, the right pair is never looked at, and the false shoots straight up.
Watch it walk

p = [1,2,1], q = [1,1,2] — same shape, values swapped:

text
   p:   1          q:   1        roots match (1 = 1)
       / \             / \
      2   1           1   2

   left pair:  (2, 1)  -> values differ -> FALSE
   right pair: never checked (the AND already collapsed)

Answer false — and note comparing sorted contents would wrongly pass this, since both hold {1,1,2}. Position matters.

The idea to reuse

Worst case every position is compared once: O(min(N, M)) time (the walk stops as soon as one tree runs out), O(H) stack. The reusable shape is the paired recursion: when a question is about two structures, recurse on both together and let a local disagreement at any pair settle it. The skeleton is fixed — both-empty, one-empty, local check, then paired recursive calls — and only the local check and the pairing change from problem to problem.

Interactive Strategy Visualization

Same Tree Audit

Parallel Structure Verification

123123
Scanning Topology...
Lockstep Analysis

Checking root values. Both are 1.

"Both Null? True. Diff Vals? False."

Strategy

Parallel traversal ensures structural equality. catch differences immediately.

"Base-case focused recursion."

O(N) Time · O(N) Space Serialize Both And Compare
→
O(min(N,M)) Time · O(H) Space Paired Lock-step Walk