LeetCode 100 · Easy · Trees

Same Tree

Given the roots of two binary trees p and q, decide whether they are identical: the same shape, with equal values in matching positions.

O(n)time · n = smaller tree
O(h)space · call stack
DFS in lockstepcompare pairs, stop at the first miss

level order as on LeetCode, null = no child · each tree up to 15 nodes, 4 levels · values −99 to 99

p

q

Call stack one frame per isSameTree(p, q) call, shown as p,q · N = null · badges = returned ✓ / ✗

public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p != null && q != null && p.val == q.val) { return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } return false;}
p
—
q
—
left
—
right
—
return
—

Why it works

  1. Brute force serializes both trees with null markers and compares the strings. Also O(n), but it builds two full strings even when the roots already differ.
  2. Two trees are the same exactly when the roots match and the left subtrees are the same and the right subtrees are the same. The code is that sentence, walked in lockstep on matching positions.
  3. Each pair of nodes is compared once, and the walk stops at the first mismatch thanks to &&: O(min(n, m)) time, O(h) stack.
  4. Pitfall: checking only values. A null against a node is a mismatch even if every value matches, as in [1,2] vs [1,null,2]. The two null checks must come before p.val is read.
  5. Next: Subtree of Another Tree (572) runs this exact check from every node of the bigger tree.