Symmetric Tree — LeetCode 101 Mirror Recursion Pattern

Problem Statement#

Given the root of a binary tree, check whether it is a mirror of itself (i.e. symmetric around its center).

Constraints:

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

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

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

Why This Problem Matters#

LeetCode 101 — Symmetric Tree is a phone-screen staple at Amazon, Microsoft, Bloomberg, and Meta. It is the natural follow-up to Invert Binary Tree because both problems are about mirroring, but here you must compare two halves without mutating the tree.

Interviewers like it because it forces candidates to introduce a helper function with two parameters — a small leap that catches engineers who only know "single-pointer recursion". Once you grasp the dual-pointer pattern, the same template solves Same Tree, Merge Two Binary Trees, and Subtree of Another Tree.

It is also a clean way to test BFS comprehension: the iterative version uses a queue with paired insertion order. Expect this question if your phone screen is 30 minutes and the role is mid-level (L4/SDE2) or below.

The Core Insight#

A tree is symmetric iff its left subtree is a mirror of its right subtree. Two subtrees A and B mirror each other when:

1. A.val == B.val
2. A.left mirrors B.right
3. A.right mirrors B.left

That cross-comparison (left-of-A with right-of-B) is the whole trick. Run a recursive helper isMirror(a, b) and you are done.

Visual Dry Run#

Tree [1,2,2,3,4,4,3]:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

Final answer true.

Solution (Optimal)#

# Python — recursive mirror helper
class Solution:
    def isSymmetric(self, root):
        def mirror(a, b):
            if not a and not b: return True
            if not a or not b:  return False
            return (a.val == b.val
                    and mirror(a.left,  b.right)
                    and mirror(a.right, b.left))
        return mirror(root, root)

// JavaScript — same recursion
var isSymmetric = function(root) {
    const mirror = (a, b) => {
        if (!a && !b) return true;
        if (!a || !b) return false;
        return a.val === b.val
            && mirror(a.left,  b.right)
            && mirror(a.right, b.left);
    };
    return mirror(root, root);
};

# Iterative BFS — push pairs into the queue
from collections import deque
class Solution:
    def isSymmetric(self, root):
        q = deque([(root, root)])
        while q:
            a, b = q.popleft()
            if not a and not b: continue
            if not a or not b:  return False
            if a.val != b.val:  return False
            q.append((a.left,  b.right))
            q.append((a.right, b.left))
        return True

Time: O(n) — each node is compared exactly once. Space: O(h) for recursion, O(w) for BFS queue.

Common Mistakes#

• Comparing a.left with b.left instead of a.left with b.right — that checks "are the two halves equal", not "are they mirrors".
• Forgetting the not a and not b -> True base case before the not a or not b -> False check.
• Building a string serialization and comparing with its reverse — works but uses O(n) extra space and breaks on duplicate values.
• Mutating the tree by inverting one half then comparing — destroys the input and is a flag in code review.

Interview Tips#

• Restate the definition: "symmetric means the left subtree is a mirror of the right subtree".
• Define isMirror(a, b) on the whiteboard before writing the public function.
• Mention BFS as an iterative fallback if the interviewer asks about deep trees.
• Clarify "do null nodes count as symmetric?" before coding — yes, two nulls are mirrors.

Follow-up Questions#

• Same Tree (LC 100)? Drop the cross-recursion; compare left==left and right==right.
• Subtree of Another Tree (LC 572)? Walk the larger tree and call isSameTree at every node.
• Symmetric N-ary tree? Reverse the children list of one side before comparing pairwise.
• Iterative without queue? Use two stacks pushed in opposite child orders.
• Memory-bound version? Morris traversal of left subtree compared with reverse Morris of right.

Key Takeaways#

• LeetCode 101 Symmetric Tree runs in O(n) time and O(h) space.
• The trick is a two-pointer helper isMirror(a, b) that swaps left/right on each recursion.
• A tree is symmetric iff a.val == b.val, a.left mirrors b.right, and a.right mirrors b.left.
• Asked at Amazon, Microsoft, Bloomberg, Meta as a phone-screen warmup.
• BFS with paired queue insertion is the iterative alternative.
• Companion to Invert Binary Tree (LC 226) — same mirror logic without mutation.
• Foundation for Same Tree (LC 100) and Subtree of Another Tree (LC 572).