Intuition
Symmetry is Same Tree with a twist: compare the left subtree against the mirrored right subtree. So the recursion pairs a.left with b.right and a.right with b.left.
Symmetry is same-tree with one pairing changed. Instead of comparing left-to-left, you compare each subtree against its mirror — left against right. Whenever a problem is about reflection rather than equality, look for the place where the recursive call's arguments should cross over.
Approach
Mirror comparison
mirror(a, b) = a.val == b.val AND mirror(a.left, b.right) AND mirror(a.right, b.left).
Start with the root's children
The root always mirrors itself; the question is mirror(root.left, root.right).
Iterative variant
A queue of node pairs does the same pairing breadth-first — useful when recursion depth is a worry.
Solution & live demo
Common pitfalls
Recursing on matching sides instead of mirrored ones
return (a.val == b.val
and mirror(a.left, b.left)
and mirror(a.right, b.right))return (a.val == b.val
and mirror(a.left, b.right)
and mirror(a.right, b.left))That tests whether the two subtrees are identical, not mirrored — it would reject [1,2,2,3,4,4,3], which is symmetric. A reflection maps the leftmost node to the rightmost, so the calls must cross.
Comparing the root with itself
return mirror(root, root)
return not root or mirror(root.left, root.right)
It happens to work, because crossing the arguments makes the root trivially match itself — but it obscures the actual claim, which is that the root's two children are mirrors of each other. Starting from the children states the invariant you're relying on.
Edge cases
Shape matches but not mirrored (both 3s on the same side) → False — the cross-pairing catches it.
Symmetric by convention → True.