Symmetric Tree

Given the root of a binary tree, return true if it is symmetric — a mirror image of itself around its center — and false otherwise.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

A tree is symmetric when its left subtree is the mirror image of its right subtree.

Two subtrees mirror when their roots are equal and the outer and inner child pairs mirror.

It's the same-tree comparison, but with the recursion crossed: a.left vs b.right, a.right vs b.left.

Common doubts

Only the recursion crosses the children: mirror(a.left, b.right) and mirror(a.right, b.left) instead of (left,left) and (right,right).

A mirror flips left and right, so a node's left child must match the mirrored node's right child (outer), and vice versa (inner).

Yes — it trivially mirrors itself, as does the empty tree.

Interview follow-ups

· What an interviewer asks next.

Swap every node's left and right children recursively (invert binary tree).

Yes — a level-order or preorder serialization with null markers should read as a palindrome per level, though the crossed recursion is cleaner.

Fun facts

Symmetric-tree is the same-tree algorithm with the child comparisons crossed.
Inverting a tree and then running the same-tree check against the original is an equivalent (if wasteful) way to test symmetry.

Asked at

AmazonMicrosoftFacebook

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: true
The left and right subtrees are mirror images of each other.

Example 2

Input: root = [1, 2, 2, null, 3, null, 3]
Output: false
The 3s are both on the inner side rather than mirrored, breaking symmetry.

Constraints

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

A tree is symmetric when its left subtree is the mirror of its right subtree. Two subtrees mirror each other when their roots are equal and — the key twist — the outer children match (a.left with b.right) and the inner children match (a.right with b.left). It's the same-tree comparison with the recursion crossed.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary tree. Nodes with a value and up to two children (left, right).

Parallel recursion. Comparing two subtrees at once — here, crosswise.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Symmetric by structure and values?”

Both — the mirror must match in shape and in node values.

“Is an empty tree symmetric?”

Yes, trivially.

The ideal opening — say it like this

A tree is symmetric if its left and right subtrees are mirror images.

Two subtrees mirror when their roots are equal and the outer pair (a.left vs b.right) and inner pair (a.right vs b.left) also mirror.

Understand the problem

Worked example — tree [1, 2, 2, 3, 4, 4, 3]

        1
       / \
      2   2
     / \ / \
    3  4 4  3
mirror(2,2): outer 3 vs 3 ✓, inner 4 vs 4 ✓
answer: true

Key observations

1Aha

Symmetric = left subtree mirrors right subtree

The whole check reduces to one call: mirror(root.left, root.right).

2Aha

Cross the recursion

Mirror compares a.left with b.right and a.right with b.left — the crossing is what encodes 'mirror image'.

3Aha

It's same-tree, crossed

Swap the two recursive pairings back to (left,left) and (right,right) and you get the same-tree check.

Brute force vs optimal

	Iterative (queue of mirrored pairs)	Recursive mirror
Idea	Compare outer/inner pairs from a queue	roots equal AND outer mirror AND inner mirror
Time	O(n)	O(n)
Space	O(n)	O(height)

Both are O(n); the recursion is a direct transcription. Full code is in the Approaches selector below.

Summary

Key takeaway

A tree is symmetric iff its left subtree mirrors its right. Two subtrees mirror when roots are equal and outer (a.left↔b.right) and inner (a.right↔b.left) pairs mirror. O(n) time, O(height) space.

mirror(a, b):
    if a is null and b is null: return true
    if a is null or b is null or a.val != b.val: return false
    return mirror(a.left, b.right) and mirror(a.right, b.left)