LeetCode 100 · Trees · concept: trees
Problem
Return true if two binary trees are identical in structure and values.
Approach — parallel recursion (optimal)
Walk both trees in lockstep: same node must be both-null or both-present with equal values and matching subtrees.
def isSameTree(p, q):
if not p and not q:
return True # both empty here -> match
if not p or not q or p.val != q.val:
return False # one empty, or values differ -> mismatch
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)Time O(n), space O(h).
The base cases carry the logic
Three conditions cover everything: both null (match), exactly one null or unequal values (mismatch), otherwise recurse on both child pairs. The and means any single mismatch anywhere collapses the whole result to False.
Key insight
Compare two trees by recursing on both simultaneously. This “parallel DFS over a pair of structures” is the reusable primitive — it’s the subroutine called at every node of Subtree of Another Tree and mirrors the structure of symmetric-tree checks.
Related
- concept: trees, dfs
- prev: Balanced Binary Tree · next: Subtree of Another Tree
Software engineering
Infrastructure & security
Computer science
Hardware & engineering