Mirror Symmetry Check
Problem
Decide whether a binary tree is a mirror image of itself, as if a vertical line ran down through the root. Both the shape and the values have to match across that line. An empty tree counts as symmetric.
Examples
Input: tree = 1, left 2 with children 3 and 4, right 2 with children 4 and 3
Output: True
Why: the right subtree is the left subtree read back to frontInput: tree = 1, left 2 with right child 3, right 2 with right child 3
Output: False
Why: the two threes hang on the same side, so the shape is not mirroredInput: tree = empty
Output: True
Why: edge case, nothing is trivially symmetricHints
0 / 3
Symmetry is not a property of one node at a time, it is a property of pairs of nodes that face each other across the middle line.
Ask a different question than the obvious one: instead of is this tree symmetric, ask are these two subtrees mirror images of each other.
Compare the left and right subtrees of the root as a pair. Two subtrees mirror each other when both are absent, or both are present with equal values and the left child of one mirrors the right child of the other, in both directions.
Solution
The natural recursion is over pairs rather than single nodes: two subtrees mirror each other when their roots agree and their children mirror crosswise, outer against outer and inner against inner. The base case has to distinguish both absent, which is a match, from one absent, which is a shape mismatch, and an identity comparison covers both at once. Every node is visited once. Time is O(n), and space is O(h) for the call stack.
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_symmetric(root):
def mirrors(a, b):
if a is None or b is None:
return a is b # true only when both are absent
# outer child against outer child, inner child against inner child
return (a.val == b.val and mirrors(a.left, b.right)
and mirrors(a.right, b.left))
return root is None or mirrors(root.left, root.right)
print(is_symmetric(T(1, T(2, T(3), T(4)), T(2, T(4), T(3))))) # -> True
print(is_symmetric(T(1, T(2, None, T(3)), T(2, None, T(3))))) # -> False
print(is_symmetric(None)) # -> TrueStuck on the idea rather than the code? Binary Trees covers it.