#132

Symmetric Tree

easy

treedepth-first-searchbreadth-first-searchbinary-tree

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

A tree is symmetric when its left subtree is the mirror image of its right subtree: matched nodes hold equal values, and a left child on one side corresponds to a right child on the other.

The tree is given as a level-order array where null marks a missing child: [1, 2, 2, 3, 4, 4, 3] is symmetric.

Example

Input: root = [1,2,2,3,4,4,3]3241423

Output: true

The left subtree mirrors the right: 2=2, 3↔3, 4↔4.

Constraints

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

Intuition

A tree is symmetric when it's a mirror of itself. The tempting first move is to build the mirror — invert the tree into a copy — and check whether the copy equals the original. It's correct, but it allocates a whole second tree to answer a yes/no question.

function isSymmetric(root) {
  // Deep-copy the tree with its children swapped (the mirror).
  const mirror = (node) =>
    node ? { val: node.val, left: mirror(node.right), right: mirror(node.left) } : null;
  // Compare two trees node for node.
  const equal = (a, b) =>
    (!a && !b) || (!!a && !!b && a.val === b.val && equal(a.left, b.left) && equal(a.right, b.right));
  return equal(root, mirror(root));
}

Brute force — invert a copy of the tree, then compare it to the original: O(n) time, O(n) space.

This is O(n) time but allocates a full mirror copy. Can we do better on space?

The key observation: symmetry is a property of a pair of subtrees, not of one tree, so we never need to build anything — just compare the left subtree against the right subtree directly. Two subtrees mirror when their roots match and the left's left mirrors the right's right (the outer pair) and the left's right mirrors the right's left (the inner pair). The two recursive calls cross over — that crossing is the whole trick.

This is the same paired-recursion idea as Same Tree, but with the child comparisons flipped.

Tracing [1, 2, 2, 3, 4, 4, 3] — root 1 with two 2-subtrees:

Roots of the pair: left 2 and right 2 — equal, continue.
Outer pair: left-2's left (3) vs right-2's right (3) — equal leaves, mirror ✓.
Inner pair: left-2's right (4) vs right-2's left (4) — equal leaves, mirror ✓.

All pairs match, so the tree is symmetric. A value mismatch or a shape mismatch (one child present, the other null) at any pair returns false immediately.

The mechanic is a structural cross-comparison of two subtrees, which a single scanned lane can't depict — the trace narrates the outer/inner pairing instead.
The base cases carry the shape check: both-null is a match; exactly-one-null is a mismatch (the two sides have different shapes there).

Optimization

Mirror recursion on a pair

Symmetry is a property of two subtrees, so recurse on pairs: compare the left subtree against the right subtree. Two nodes mirror when their values match and the left's left mirrors the right's right and the left's right mirrors the right's left — the outer and inner pairs cross.

O(n) time (each node compared once), O(h) recursion space.

function isSymmetric(root) {
  // Do two subtrees mirror each other?
  const mirror = (a, b) => {
    if (!a && !b) return true;        // both empty: trivially mirrored
    if (!a || !b) return false;       // one empty, one not: shape differs
    if (a.val !== b.val) return false; // values must match
    // Outer pair (a.left vs b.right) and inner pair (a.right vs b.left) cross.
    return mirror(a.left, b.right) && mirror(a.right, b.left);
  };
  return mirror(root?.left ?? null, root?.right ?? null);
}

Complexity analysis

Time complexity: O(n). Here's why:

The paired recursion compares each node against its mirror partner exactly once.
Each comparison is O(1).

So O(n) overall, and it short-circuits to less on the first mismatch.

Space complexity: O(h). Here's why:

The recursion descends both sides in lockstep, so the stack depth is the tree height h.

O(log n) balanced, O(n) worst case. Unlike the brute force, no mirror copy is allocated.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = [7]7	true	Single node — trivially symmetric.
root = [9,4,4]494	true	Two equal leaves mirror each other.
root = [6,2,2,8,null,null,8]82628	true	Outer children cross-match (left-2's left mirrors right-2's right).
root = [6,2,2,8,null,8,null]82682	false	Left-2 has a left child, right-2 a left child too — they don't mirror.
root = [5,7,9]759	false	Root's two children differ in value.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor