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

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


def isSymmetric(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 and O(n) extra space for the full mirrored copy. That second tree is unnecessary: the comparison can be done in place by walking the original tree against itself.

Approach 2 — Recursive mirrored lockstep

Symmetry of a tree is mirror-equality between two trees: the root’s left and right subtrees. Reuse the Same Tree lockstep DFS with one change. 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


def isSymmetric(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)

On Example 1, the mirror axis runs down the middle. The outer children (3, 3) pair up and the inner children (4, 4) pair up:

graph TD
    R[1]
    L2[2 left]
    R2[2 right]
    L3[3]
    L4[4]
    R4[4]
    R3[3]
    R --> L2
    R --> R2
    L2 --> L3
    L2 --> L4
    R2 --> R4
    R2 --> R3

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

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 answers the follow-up to solve 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


def isSymmetric(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 crux of the 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 child pairings 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 involves 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.