Symmetric Tree: Mirrored Recursion on One Tree

"Symmetric Tree" shows up again and again in Meta, Amazon, Microsoft phone screens. It is a Easy problem on paper, but the real test is whether you recognize the Tree DFS pattern quickly and code it cleanly. Part 4 of 11 in the Tree DFS arc.

The Problem

Return whether a binary tree is a mirror of itself around its center. The insight: symmetry is a pairwise property — compare the left subtree against the right subtree with the comparison itself mirrored at every level.

Input:  root = [1, 2, 2, 3, 4, 4, 3]
Output: True
[1, 2, 2, None, 3, None, 3] is False.

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

One tree, but the recursion runs on two cursors — Same Tree with crossed children: outer pairs (left.left vs right.right) and inner pairs (left.right vs right.left). Spotting that a single-structure question hides a two-cursor walk is the transferable skill.

The Approach

Helper mirror(a, b): both None is True; one None or unequal values is False; otherwise mirror(a.left, b.right) and mirror(a.right, b.left). Root call: mirror(root.left, root.right).

Iteratively, push pairs onto a stack in mirrored order — the pair-stack from Same Tree with the crossing baked into what gets pushed. Recursion bans cost you nothing if you carry that pattern.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def is_symmetric(root: TreeNode | None) -> bool:
    """True if the tree mirrors itself around its center."""

    def mirror(a: TreeNode | None, b: TreeNode | None) -> 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 mirror(a.left, b.right) and mirror(a.right, b.left)

    return mirror(root.left, root.right) if root else True

Complexity

• Time: O(n) — each node participates in exactly one pair comparison
• Space: O(h) — mirrored recursion depth

Interview Tips and Follow-Ups

• The crossed recursion (a.left with b.right) is the entire question — if you write uncrossed children you have solved Same Tree by accident.
• Level-order alternative: check each level is a palindrome including None gaps — valid, but the gaps requirement is easy to fumble; mention, don't choose.
• Follow-up families: count symmetric subtrees, or make a tree symmetric with minimum edits — both build on this helper.

More Tree DFS problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.