Symmetric Tree

Difficulty: Easy

Problem

Given the root of a binary tree, return true if the tree is a mirror of itself around its center. Imagine folding the tree down the middle along a vertical line through the root — it is symmetric exactly when the two halves line up perfectly, node for node and value for value.

Example

Input: root = [1,2,2,3,4,4,3]
Output: true
Explanation: The left subtree and the right subtree are mirror images of each other: the 2s face each other, the outer 3s match, and the inner 4s match. Fold the tree down the middle and every node lands on a partner with the same value.

Brute-force approach

There is no meaningful 'brute force vs optimal' split here — the crossed recursive comparison IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: Same Tree compared straight pairs; Symmetric Tree compares CROSSED pairs. One crossing turns 'equal' into 'mirrored'.

Compare the left and right halves of the tree in lock-step, exactly like Same Tree — but walk them in OPPOSITE directions. Each mirror(a, b) call runs the familiar three checks, then recurses into the CROSSED children: the outer pair and the inner pair.

Steps

  1. Define a helper mirror(a, b): are the subtrees at a and b mirror images of each other?
  2. If a and b are both null, return true — two empty spots mirror perfectly
  3. If exactly one of them is null, or their values differ, return false
  4. Recurse CROSSED: mirror(a.left, b.right) AND mirror(a.right, b.left)
  5. Kick everything off with mirror(root.left, root.right) — the root always matches itself

Time complexity: O(n) · Space complexity: O(h)