Symmetric Tree — Solution

Problem

Given the root of a binary tree, check whether it is a mirror of itself — meaning the left and right subtrees are perfect reflections of each other, not just equal.

Example:

[1,2,2,3,4,4,3]

• Input: root = [1, 2, 2, 3, 4, 4, 3]
• Output: true
• Explanation: The left subtree mirrors the right — outer children (3, 3) match, inner children (4, 4) match.

Counter-example (not symmetric):

[1,2,2,null,3,null,3]

• Output: false — the left subtree has no left child but the right subtree does.

Intuition

Symmetry is a recursive structural property: two subtrees are mirrors when their root values are equal and the outer children mirror each other (left.left ↔ right.right) while the inner children mirror each other (left.right ↔ right.left). A single recursive helper that encodes this pairing handles every case cleanly in one pass.

Solution — Recursive Mirror Check

Define a helper is_mirror(left, right) that checks whether two subtrees are mirrors of each other. Call it with the root's two children to compare the two halves.

Steps:

1. Call is_mirror(root.left, root.right)
2. If both nodes are null, they're trivially mirrored — return true
3. If exactly one is null, there's a structural mismatch — return false
4. If the values differ, return false
5. Recurse on the outer pair: is_mirror(left.left, right.right)
6. Recurse on the inner pair: is_mirror(left.right, right.left)
7. Both must return true for the current pair to be a mirror

1class Solution:
2    def isSymmetric(self, root):
3        def is_mirror(left, right):
4            if left is None and right is None:
5                return True   # both absent — trivially symmetric
6            if left is None or right is None:
7                return False  # one present, one absent — structural mismatch
8            if left.val != right.val:
9                return False  # values differ
10            # outer pair (left.left vs right.right) AND inner pair (left.right vs right.left)
11            return is_mirror(left.left, right.right) and is_mirror(left.right, right.left)
12
13        return is_mirror(root.left, root.right)

• Time: O(n) — every node is visited exactly once
• Space: O(h) — recursion depth equals tree height; O(log n) for balanced trees, O(n) worst case for a skewed tree

Complexity Summary

Common Mistakes

• Swapping the mirror pairs: Comparing left.left with right.left instead of right.right — symmetry requires crossing over (outer with outer, inner with inner), not straight-down comparison.
• Checking values before nulls: Calling left.val != right.val before confirming neither node is null causes a null pointer error at leaf boundaries.
• Passing root instead of its children: Calling is_mirror(root, root) returns true for any non-null tree. The correct entry call is is_mirror(root.left, root.right).
• Confusing symmetry with equal levels: Checking that each BFS level's values form a palindrome is not equivalent — a skewed tree can produce palindromic levels without being symmetric when nulls are omitted.

Related Problems

• same-tree — the mirror check is essentially same-tree with children swapped
• invert-binary-tree — constructs the exact mirror image this problem tests for
• maximum-depth-of-binary-tree — same recursive pattern: base cases + recurse on both children
• balanced-binary-tree — same structure: recursive structural property check on paired children
• path-sum — another recursive tree traversal with a clear base case