The tell: Structural equality of two trees, compared position by position.
How you get there
1Both empty means equal; one empty means not.
2Values must match, then both subtrees must match.
3Short-circuit evaluation stops at the first difference.
Solution
Python
def is_same_tree(p, q) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
Time
O(n)
Space
O(h)
What goes wrong
Comparing only values while ignoring shape accepts trees that differ structurally.