A design system stores a page as a binary tree of panels. QA wants a palindrome check: does the left column mirror the right? The intern cloned the tree, inverted the clone, and ran Same Tree against the original. Palindrome layouts returned true. A million-node page still built a whole extra tree the check never needed to keep.

A tree is symmetric only if a simultaneous walk sees mirrors: left.left with right.right, left.right with right.left. The binary tree post owns shape and traversals. Invert mutates children. Same Tree walks left with left. Here we only compare, and we cross the children.

The problem

Given the root of a binary tree, return whether it is a mirror of itself — the left subtree is a reflection of the right. An empty tree is symmetric. A single node is.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees:

      1
     / \
    2   2
   / \ / \
  3  4 4  3     →  true

      1
     / \
    2   2
     \   \
      3   3     →  false

[]                          →  true
[1]                         →  true

Note: Matching values on both sides is not enough. The second drawing has two 2s and two 3s and still fails: each 3 hangs on the same side. Do not pair left with left — that is Same Tree on the two children, and it accepts a copy, not a mirror.

Invert a copy, then Same Tree, is the honest brute force

Clone a subtree, invert the clone, then ask whether that result is the same tree as the other subtree. Correct. Extra nodes: a second tree you discard after the compare.

boolean isSymmetricCopy(TreeNode root) {
    if (root == null) {
        return true;
    }
    return isSameTree(invertCopy(root.left), root.right);
}

invertCopy and isSameTree are the helpers from Invert and Same Tree. Inverting root.left in place, then comparing it to root.right, also returns the right boolean — and mutates the caller’s tree. You paid O(n) extra nodes — or a destructive swap — for a question that only asked you to compare.

Pair the mirrors, fail on the first mismatch

Both null: symmetric. Exactly one null: not. Both present but values differ: not. Otherwise the outer children must match and the inner children must match.

mirror(2, 2)  values match
  mirror(null, 3)  one null  →  false

That is the Same Tree four-way check with the pairing crossed. Short-circuit on && so an outer mismatch never walks the inners.

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

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

Time is O(n) — each paired node is checked once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit queue of pairs is the same bound without blowing the JVM stack.

Empty tree: root is null, return true. One node: both children null, mirror(null, null) returns true. No extra branch. You never swap a child pointer.

What interviewers usually poke next

  • Same-side walk. isSameTree(root.left, root.right) is Same Tree on the two children. It accepts a copy, not a mirror. Cross the pairing.
  • Invert then compare. Related idea, different contract: that mutates (or copies). This only reads.
  • Iterative pair walk. An ArrayDeque of (a, b) pairs, same four-way check, no recursion. Mention it; write it if they ask.
  • Two inner 3s. Draw the second sample. Same keys, same-side children, not symmetric.

You are done with this problem when you can reject that second drawing without allocating a mirrored copy, and you can name the empty-tree and single-node returns without a special case.