Symmetric Tree Check, in depth: the mirror invariant, recursive and iterative solutions, traps that look correct, and checking every subtree in linear time

The problem, stated precisely

Two trees A and B are mirrors of each other when both are empty, or when both are non-empty, their roots hold equal values, A's left subtree mirrors B's right subtree, and A's right subtree mirrors B's left subtree. A tree is symmetric when it is empty or when its root's left and right subtrees are mirrors of each other.

Note what this definition includes. Shape matters as much as values: a missing child on one side must be matched by a missing child in the mirrored position on the other side. A tree with a single node is symmetric. An empty tree is symmetric. The root's own value never needs to be compared with anything, because it sits on the axis.

In LeetCode's level-order notation, [1,2,2,3,4,4,3] is symmetric, and [1,2,2,null,3,null,3] is not: both 3s hang to the right of their parents, so folding the tree puts one of them on top of an empty slot.

From first principles: compare pairs, not nodes

The key move is to stop thinking about single nodes. Symmetry is a property of pairs of positions that the fold maps onto each other. Start with the pair (root.left, root.right). If that pair matches, the fold produces two new pairs: the outer pair (left.left, right.right) and the inner pair (left.right, right.left). Every pair either matches and spawns two more, or is a pair of empty slots and spawns nothing, or fails and ends the search.

This gives an invariant that any correct implementation must preserve: every pair you examine consists of two positions that are mirror images of each other. Pushing (L.left, R.left) instead of (L.left, R.right) breaks the invariant, and the result is a check for equality of the two halves, not mirror symmetry. That is the single most common bug in submitted solutions.

The recursive solution

The definition is already recursive, so the code is a direct transcription. The helper takes a pair, handles the two base cases (both empty, exactly one empty) and then compares values and recurses on the outer and inner pairs.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right


def is_symmetric(root):
    def mirror(a, b):
        if a is None and b is None:
            return True                      # two empty slots match
        if a is None or b is None:
            return False                     # shape differs
        return (a.val == b.val
                and mirror(a.left, b.right)  # outer pair
                and mirror(a.right, b.left)) # inner pair
    return root is None or mirror(root.left, root.right)

The and chain short-circuits, so the function stops at the first mismatch. Order the checks cheapest first: comparing values before recursing avoids descending into subtrees that already disagree at their roots. The Java version is the same shape:

static boolean isSymmetric(TreeNode root) {
    return root == null || mirror(root.left, root.right);
}

static boolean mirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
}

If the values are objects rather than primitive ints, compare them with Objects.equals(a.val, b.val) in Java; == on boxed integers compares references and fails for values outside the small-integer cache.

Worked example: tracing the pairs

Run the iterative version below on the symmetric tree [1,2,2,3,4,4,3] and log every pair it takes off the queue. It examines seven pairs: the root's children, then the outer and inner pairs at depth two, then four pairs of empty slots under the leaves.

Now the asymmetric tree [1,2,2,null,3,null,3]. Step 1 compares (2, 2) and adds the outer pair (left.left, right.right), which is (empty, 3), and the inner pair (left.right, right.left), which is (3, empty). Step 2 takes the outer pair, finds exactly one side empty, and returns false. The values never disagreed; the shape did. Any solution that compares only values would get this tree wrong.

The iterative solution: a queue of pairs

Replacing recursion with an explicit container removes the stack-depth limit and makes the pair invariant visible in the code. Each entry in the queue is a pair of mirrored positions.

from collections import deque


def is_symmetric_iter(root):
    if root is None:
        return True
    pairs = deque([(root.left, root.right)])
    while pairs:
        a, b = pairs.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
        pairs.append((a.left, b.right))   # outer pair
        pairs.append((a.right, b.left))   # inner pair
    return True

With a FIFO queue the pairs are examined level by level, which finds a mismatch near the root quickly. Swap popleft for pop and you get a depth-first stack instead; both are correct, because correctness depends only on which positions are paired, not on the visiting order. The breadth-first version holds up to roughly one level's worth of pairs, the depth-first one roughly one root-to-leaf path's worth, so choose the stack for wide, shallow trees and the queue when early mismatches near the top are likely. For more on that trade-off, see BFS and DFS.

Complexity and the recursion-depth trap

Each node takes part in at most one pair, and each pair costs constant work, so the time is O(n) for n nodes. The worst case is a symmetric tree, where every pair must be checked; an asymmetric tree usually exits early. Extra space is O(h) for the recursive version, where h is the height, and O(w) for the breadth-first version, where w is the widest level.

For a balanced tree h is about log n and recursion is harmless. For a degenerate tree it is not. Consider a V-shaped tree: a root whose left child has only left children and whose right child has only right children, with equal values on both arms. It is symmetric, and its height equals its arm length. On CPython 3.13, whose default recursion limit is 1,000, the recursive function returned True for an arm of 900 nodes and raised RecursionError for an arm of 1,000; the iterative version handled 5,000 without trouble. In Java the limit depends on the thread stack size rather than a counter, so the failure point varies by JVM settings, but the failure is a StackOverflowError all the same.

Raising the limit with sys.setrecursionlimit only moves the cliff and can crash the interpreter if the C stack runs out first. If the input comes from users, files or other systems, use the iterative version.

Approaches that look right and are wrong

Three shortcuts pass the obvious examples and fail on others. Each has a concrete counterexample.

• In-order traversal is a palindrome. The in-order sequence of a symmetric tree is always a palindrome, but the converse is false. The tree [1,2,2,2,null,2] has a left 2 with a left child 2 and a right 2 with a left child 2. Its in-order sequence is 2, 2, 1, 2, 2, a palindrome, yet the tree is not symmetric: the right subtree's child should be on the right. Traversals without empty markers lose shape.
• Each level, read left to right without gaps, is a palindrome. The same tree defeats this: its levels are [1], [2, 2] and [2, 2], all palindromes. You can rescue the idea by recording empty slots as markers on every level, but by then you have reinvented the pair queue with more memory.
• Mirror the tree, then compare it with the original. This is correct, but it either mutates the caller's tree or allocates a full copy, and it always does the full O(n) work even when the root's children differ. Mirror a copy only when you need the mirrored tree for something else.

A serialisation that writes the left subtree in normal pre-order and the right subtree in mirrored pre-order, both with explicit empty markers, is correct: the two strings are equal exactly when the subtrees are mirrors. For [1,2,2,2,null,2] they come out as 2 2 # # # and 2 # 2 # #, which differ. It costs O(n) extra memory, so prefer it only when you want to store or ship the fingerprint.

Checking every subtree at once

Sometimes the question is not whether the whole tree is symmetric but which subtrees are, for example when deduplicating mirrored layout fragments. Running the pair check from every node costs O(n) per node and O(n squared) overall. A linear-time approach gives each subtree two identifiers, one for the subtree as stored and one for its mirror image, drawn from a single table so that equal identifiers mean structurally identical trees.

def symmetric_subtrees(root):
    table = {(None,): 0}               # id 0 is the empty tree
    fid, mid = {None: 0}, {None: 0}    # forward id and mirror id per node
    order, stack = [], [root] if root else []
    while stack:                       # iterative preorder; reversed, it visits children first
        n = stack.pop()
        order.append(n)
        if n.left: stack.append(n.left)
        if n.right: stack.append(n.right)
    out = set()
    for n in reversed(order):
        fid[n] = table.setdefault((n.val, fid[n.left], fid[n.right]), len(table))
        mid[n] = table.setdefault((n.val, mid[n.right], mid[n.left]), len(table))
        if fid[n.left] == mid[n.right]:   # left subtree equals mirror of right subtree
            out.add(n)
    return out

Because the table interns exact tuples rather than hashing them into fixed-width numbers, two subtrees get the same identifier only if they are identical; there are no collisions to reason about. Dictionary operations make it expected O(n). If you replace the table with a cryptographic hash so that identifiers can be compared across machines, you get a Merkle-style fingerprint, with the usual trade-off between compactness and a negligible collision probability; see Merkle trees. This function was checked against the pair check on 2,000 random trees and agreed on every node.

Testing it properly

Hand-written examples miss the cases that matter. A property test generates its own: build a random tree X, construct a root whose left child is X and whose right child is a mirrored copy of X, and assert the result is symmetric. Then change one value in the right half and assert it is not. Add the fixed edge cases explicitly.

def mirror_copy(t):
    return None if t is None else Node(t.val, mirror_copy(t.right), mirror_copy(t.left))

for _ in range(2000):
    half = random_tree(random.randrange(15))
    whole = Node(0, half, mirror_copy(half))
    assert is_symmetric_iter(whole)
    right_nodes = nodes(whole.right)
    if right_nodes:
        random.choice(right_nodes).val += 10   # outside the generated value range
        assert not is_symmetric_iter(whole)

for tree, want in [([], True), ([1], True), ([1,2,2,3,4,4,3], True),
                   ([1,2,2,None,3,None,3], False), ([1,2,2,2,None,2], False)]:
    assert is_symmetric_iter(build(tree)) is want

Generating values from a small range, such as 0 to 2, is deliberate: repeated values are what expose shape bugs. Also run one degenerate tree several thousand nodes deep through whichever version you ship.

Variants and failure modes

• Two trees are mirrors. Call the pair helper directly on the two roots.
• Shape-only symmetry. Drop the value comparison; keep the empty-slot checks.
• N-ary trees. Pair child i of one node with child k-1-i of its partner, after checking both have k children.
• Floating-point values. Exact equality fails after arithmetic; compare within a tolerance and document it.
• Trees with parent or sibling pointers. Ignore the extra pointers in the comparison or you will loop; next-pointer trees are a common example.
• Constant extra space. Threaded traversals such as Morris traversal avoid the stack, but walking two halves in opposite directions while temporarily rewiring pointers is fiddly; the queue version is usually the better engineering choice.

What to do next

1. Write the recursive version from the definition without looking, then the queue version, and check that both push the outer and inner pairs.
2. Run both on [1,2,2,null,3,null,3] and [1,2,2,2,null,2] and confirm both return false.
3. Build a V-shaped tree a few thousand nodes deep and observe the recursive version fail in your language.
4. Add the mirror-copy property test to your test suite and run it with a small value range.
5. Implement the all-subtrees variant and compare its output with the per-node pair check on random trees.
6. Apply the pair technique to a real tree diff in your code base, such as comparing two configuration or layout trees.