Symmetric tree: is a binary tree its own mirror

Given the root of a binary tree, return whether the tree is a mirror image of itself around its centre.

Interface

Unless you agree on a different interface with the interviewer, assume:

• is_symmetric(root: TreeNode | None) -> bool — TreeNode has val, left and right. An empty tree is symmetric.

Example

is_symmetric([1, 2, 2, 3, 4, 4, 3])           ->  True
is_symmetric([1, 2, 2, None, 3, None, 3])     ->  False   # both 3s are right children
is_symmetric([])                              ->  True

(Trees are written in level order, None for a missing child.)

Constraints

• Up to 10^5 nodes; values fit in a signed 32-bit integer.

Clarifying questions

• Is an empty tree symmetric? (Yes.)
• Do values matter, or only the shape? (Both.)
• Can the tree be deep enough that recursion would overflow the stack?

What a strong answer covers

• Two subtrees mirror each other when their roots are equal, the left of one mirrors the right of the other, and the right of one mirrors the left of the other.
• A recursive mirror(a, b) helper; O(n) time, O(h) space.
• An iterative version with a queue or stack of node pairs, safe for a 10^5-deep skewed tree.
• Tests: empty tree, single node, same shape with different values, asymmetric shape.

Follow-ups

• Return the first pair of nodes that breaks the symmetry.
• Check whether two different trees are mirror images of each other.
• Make the tree symmetric with the fewest node insertions.