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)