Symmetric Tree: Mirror Recursion

You are given the root of a binary tree. Determine whether it is a mirror of itself, meaning the left half is a reflection of the right half.

This is LeetCode 101: Symmetric Tree, and it is one of the cleanest examples of mirror recursion you will find. If you have already solved Maximum Depth of Binary Tree, you know the recursive null base case pattern. Symmetric Tree builds directly on that foundation, but instead of recursing into one tree, you recurse into two subtrees at the same time and compare them as mirror pairs.

Why this problem matters

Symmetric Tree teaches you a skill that most easy tree problems do not: comparing two nodes in parallel. In Maximum Depth, you recurse into node.left and node.right independently. Here, you recurse into left.left with right.right (the outer pair) and left.right with right.left (the inner pair) simultaneously.

That "two-pointer on trees" thinking shows up again in Same Tree (LeetCode 100), Merge Two Binary Trees (LeetCode 617), and subtree-checking problems. Learning it here, where the visual symmetry makes the logic obvious, sets you up for those harder variations.

The key insight

A tree is symmetric if you can draw a vertical line through the root and every node on the left has a matching node on the right, in the mirrored position.

More precisely, two subtrees are mirrors of each other when:

1. Both are null (nothing to compare, so they match)
2. Both exist, their values are equal, and the outer pair is a mirror and the inner pair is a mirror

The outer pair means left.left vs right.right. The inner pair means left.right vs right.left. That cross-comparison is what makes it mirror recursion instead of plain recursion.

The recursive solution

def is_symmetric(root):
    if root is None:
        return True

    def is_mirror(left, right):
        if left is None and right is None:
            return True
        if left is None or right is None:
            return False
        return (left.val == right.val
                and is_mirror(left.left, right.right)
                and is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)

Let's break this down:

• if left is None and right is None: return True is the base case. Two empty nodes are mirrors of each other. This is where the recursion bottoms out.
• if left is None or right is None: return False catches the case where one node exists but the other does not. A node and a gap can never be mirrors.
• left.val == right.val checks that the mirror pair has the same value.
• is_mirror(left.left, right.right) recurses on the outer pair.
• is_mirror(left.right, right.left) recurses on the inner pair.

All three conditions must hold. If any mirror pair fails, the whole tree is not symmetric.

Visual walkthrough

Let's trace through the symmetric tree [1, 2, 2, 3, 4, 4, 3] step by step. At each step we compare one mirror pair and then recurse into the next level of pairs.

See how the recursion works in pairs rather than single nodes? Each call to is_mirror receives two nodes, checks their values, then spawns two more calls: one for the outer children and one for the inner children. When both calls return True, the pair is valid, and the result bubbles back up.

The iterative solution

You can also solve this with a queue (BFS-style). Instead of recursion, you push mirror pairs onto a queue and process them one at a time.

from collections import deque

def is_symmetric(root):
    if root is None:
        return True
    queue = deque([(root.left, root.right)])
    while queue:
        left, right = queue.popleft()
        if left is None and right is None:
            continue
        if left is None or right is None:
            return False
        if left.val != right.val:
            return False
        queue.append((left.left, right.right))
        queue.append((left.right, right.left))
    return True

The logic is identical to the recursive version. You just replaced the call stack with an explicit queue. Each iteration pops a mirror pair, checks it, and enqueues the next two pairs (outer and inner). If any pair fails, you return False immediately.

Complexity analysis

Time is O(n) for both approaches. Every node is visited at most once as part of a mirror pair comparison.

Space for the recursive approach is O(h), where h is the height of the tree, because the call stack grows as deep as the tree. For a balanced tree, h = log(n). For a completely skewed tree, h = n.

Space for the iterative approach is O(n) in the worst case, since the queue can hold up to n/2 pairs at the widest level of the tree.

Edge cases to watch for

Before submitting, consider these:

• Empty tree (root is None): return True. An empty tree is trivially symmetric.
• Single node (no children): return True. Both children are null, and two nulls are mirrors.
• Root with only one child: return False. One subtree is null and the other is not, so the first mirror check fails.
• Values match but structure differs: this is the tricky one. Two subtrees could have the same set of values but in non-mirror positions. The cross-comparison (left.left vs right.right, left.right vs right.left) catches this.

The building blocks

This problem is built on one fundamental brick: the recursive null base case pattern for trees.

def solve(node):
    if node is None:
        return BASE_VALUE
    left = solve(node.left)
    right = solve(node.right)
    return COMBINE(left, right)

For Symmetric Tree, the skeleton adapts slightly because you are comparing two nodes at once. The BASE_VALUE has two cases (both null returns True, one null returns False), and COMBINE is values_match and outer_mirror and inner_mirror. But the core idea is the same: recurse until you hit null, then combine results on the way back up.

This same recursive null base case pattern drives:

• Maximum Depth (LeetCode 104): BASE_VALUE is 0, COMBINE is 1 + max(left, right)
• Invert Binary Tree (LeetCode 226): BASE_VALUE is None, COMBINE swaps children
• Same Tree (LeetCode 100): nearly identical to Symmetric Tree, but comparing corresponding nodes instead of mirror nodes
• Balanced Binary Tree (LeetCode 110): BASE_VALUE is 0, COMBINE checks height difference

Once you internalize this recursive skeleton and the mirror-pair variation, you can solve a huge family of tree problems by just changing what the base case returns and how you combine results.

From understanding to recall

You just traced through a clean recursive solution with a visual walkthrough. The mirror pair logic makes sense right now. But will you remember the cross-comparison trick in a week? Will you instinctively write is_mirror(left.left, right.right) and is_mirror(left.right, right.left) without second-guessing which goes with which?

Understanding is step one. Recall under pressure is step two. Spaced repetition bridges that gap. You practice typing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the double-null base case, the value check, and the outer/inner recursive calls from memory.

The recursive null base case is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition beats grinding random problems every time.

Related posts

• Maximum Depth of Binary Tree - The best introduction to the recursive null base case pattern that Symmetric Tree builds on
• Invert Binary Tree - Another tree transformation problem using the same recursive skeleton, but with a swap instead of a comparison