Symmetric Tree

Problem

Given the root of a binary tree, decide whether the tree is a mirror of itself — that is, symmetric around its vertical center line. Return True if it is, False otherwise.

Symmetry is both structural and value-based: the left subtree must be the mirror image of the right subtree, with matching values at mirrored positions.

Examples

Example 1

Input: root = [1,2,2,3,4,4,3]
Output: True

Left subtree (2 → 3,4) is the mirror of the right subtree (2 → 4,3): outer children 3/3 match, inner children 4/4 match.

Example 2

Input: root = [1,2,2,null,3,null,3]
Output: False

Both 2s have their 3 as a right child. Mirrored positions would require one 3 on the right and the other on the left.

Example 3

Input: root = [1]
Output: True

A single node (and likewise an empty tree) is trivially symmetric.

Constraints

• The number of nodes is in the range [1, 1000].
• -100 <= Node.val <= 100

Follow-up: solve it both recursively and iteratively.

Think about it first

TL;DR

Mirrored lockstep DFS (isMirror(left, right)) — O(n) time, O(h) space; iterative pair-queue variant included.

Approach 1 — Brute force: build the mirror, then compare

The most literal reading: construct a mirrored copy of the whole tree (swap every node’s children), then run a standard Same Tree equality check between the original and the copy.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror(node: Optional[TreeNode]) -> Optional[TreeNode]:
            if node is None:
                return None
            return TreeNode(node.val, mirror(node.right), mirror(node.left))

        def same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
            if p is None and q is None:
                return True
            if p is None or q is None or p.val != q.val:
                return False
            return same(p.left, q.left) and same(p.right, q.right)

        return same(root, mirror(root))

Complexity: O(n) time but O(n) extra space for the full mirrored copy — allocating a second tree just to throw it away is the tell that the comparison can be done in place, by walking the original tree against itself.

Approach 2 — Recursive mirrored lockstep

The insight: symmetry of one tree is mirror-equality of two trees — the root’s left and right subtrees. Reuse the Same Tree lockstep DFS with one twist: when descending, pair each node’s left child with the other node’s right child (outer with outer, inner with inner).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True

        def is_mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
            if a is None and b is None:
                return True
            if a is None or b is None or a.val != b.val:
                return False
            return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)

        return is_mirror(root.left, root.right)

Walkthrough on Example 1 (root = [1,2,2,3,4,4,3]):

1. is_mirror(2_L, 2_R): values equal → check the crossed pairs.
2. Outer pair is_mirror(3, 3): equal, all four children are None → True.
3. Inner pair is_mirror(4, 4): equal, children None → True.
4. Both pairs true → tree is symmetric.

On Example 2, step 2 becomes is_mirror(None, 3) — the left 2 has no left child while the right 2 must offer its right child, node 3 — one-sided None → False.

Complexity: O(n) time (every node visited once), O(h) recursion space, O(n) worst case for a skewed tree.

Approach 3 — Iterative with a queue of mirrored pairs

The insight: as with any pair-lockstep recursion, an explicit worklist of pairs replaces the call stack — the only thing to preserve is the crossed enqueueing order. This is a BFS (breadth-first search) over mirrored pairs, and it satisfies the classic follow-up “now do it iteratively”.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque
from typing import Optional


class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        queue = deque([(root.left, root.right)])
        while queue:
            a, b = queue.popleft()
            if a is None and b is None:
                continue
            if a is None or b is None or a.val != b.val:
                return False
            queue.append((a.left, b.right))
            queue.append((a.right, b.left))
        return True

Walkthrough on Example 2 (root = [1,2,2,null,3,null,3]): start with (2, 2) — equal; enqueue crossed pairs (2.left, 2.right) = (None, 3) and (2.right, 2.left) = (3, None). Pop (None, 3): one-sided None → False immediately.

Complexity: O(n) time, O(w) space where w is the widest level (up to O(n)).

Common pitfalls

• Pairing children straight instead of crossed: is_mirror(a.left, b.left) checks equality, not symmetry — it wrongly accepts Example 2 and rejects valid mirrors. The cross (a.left with b.right) is the entire problem.
• Comparing value lists: checking that each level reads the same forwards and backwards misses None placement; nulls must take part, as Example 2 shows (level [null,3,null,3] vs its reverse).
• Only checking the root’s immediate children: equal child values at depth 1 say nothing about deeper structure — the recursion must go to the leaves.
• Forgetting the trivial cases: an empty tree and a single node are symmetric; make sure root is None returns True, not a crash on root.left.

Pattern takeaway

Symmetric Tree is Same Tree with the wires crossed: one structural recursion (both-None / one-None / compare-and-descend) serves both, and the only design decision is which child pairs with which. When a problem talks about mirrors, palindromic structure, or reversals over trees, look for a lockstep traversal where one side walks left-to-right and the other right-to-left.