Same Tree

Given roots p and q, decide whether the two trees are structurally identical and have the same values at corresponding nodes.

DFS · RecursionTree ComparisonLeetCode #100 · Easy

Key concepts at a glance — for those who already know the basics.

Problem Statement

Given roots p and q, return true if the two binary trees are exactly the same.

Exactly the same means both structure and values match at every corresponding node position.

Example: p=[1,2,3], q=[1,2,3] => true; p=[1,2], q=[1,null,2] => false

01 · The definition

Same structure AND same values at every corresponding node

Both trees must be null at the same positions, and where they are not null, each pair of nodes must have equal values.

02 · The key insight

1

If both nodes are null, return True

Both branches ended at the same shape position.

2

If only one is null, return False

This catches structure mismatch immediately.

3

Compare values, then recurse left AND right

Both subtree comparisons must pass.

03 · Code (Python)

class Solution:
  def isSameTree(self, p, q) -> bool:
    if not p and not q: return True
    if not p or not q: return False
    if p.val != q.val: return False
    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

04 · Complexity

Time

O(n)

Worst case visits all corresponding nodes.

Space

O(h)

Recursion depth equals tree height.

Practice on LeetCode

Try #572 (Subtree of Another Tree) next — it uses isSameTree as a direct helper.

Open on LeetCode ↗