Symmetric Tree

Given a binary tree, return true if it is a mirror of itself.

Why this is worth learning

Mirror comparison pairs the outside children and the inside children. Comparing left with left tests equality, not symmetry.

Before coding: one-minute experiment

Can equal values on the left and right roots prove symmetry when one has a left child and the other also has a left child?

Function signature

func IsSymmetric(root *TreeNode) bool

Inputs / outputs

• root: root of the tree.
• Return: true if symmetric, else false.

Example

    1
   / \
  2   2
 / \ / \
3  4 4  3
Output: true

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

Equal values at the root's two children are necessary but cannot detect asymmetric descendants. Nor do equal value multisets preserve positions. Compare corresponding positions in the imagined reflection: left.Left pairs with right.Right, and left.Right with right.Left. The state is therefore a pair of nodes, not one node plus a global bag of values. Both absent positions match; a single absent position fails. Apply the same mirror relation recursively to establish the whole shape.

Invariant: isMirror(a,b) checks symmetry of two subtrees.

Algorithm (step-by-step)

1. Define helper isMirror(a,b).
2. If both nil, return true; if one nil, false.
3. Check values and recursive mirror match.

Correctness sketch

A pair of nil subtrees is mirrored; a pair with exactly one nil subtree is not. For two real subtree roots, their values must agree. The first root's left subtree must mirror the second root's right subtree, and its right must mirror the second's left. These are exactly the positions exchanged by reflection. Applying this condition recursively is necessary and sufficient by induction on the paired subtrees. Comparing the root's left and right children in this crossed manner therefore decides whole-tree symmetry. The empty tree is symmetric.

Trace (hand walkthrough)

Example input:
    1
   / \
  2   2
 / \ / \
3  4 4  3
Output: true

Walk:
- compare root.left=2 with root.right=2
- compare left.left=3 with right.right=3
- compare left.right=4 with right.left=4 -> symmetric

Pitfalls to avoid

• Comparing left-left with right-right instead of left-right.
• Not treating nil/nil as a valid match.

Debugging lens

Use duplicate values with asymmetric missing-child positions. Equal value lists at each depth can still hide a structural asymmetry.

Complexity

• Time: O(n)
• Extra space: O(h).

Implementation notes (Go)

• Use a helper that compares (left, right) with mirrored recursion.
• Handle nil/nil as a valid match.

Reconstruction checkpoint

Two children of a root both have value 4. Each of those children has only a left child of value 7. Is the whole tree symmetric? State the node pair that disproves it.

Return to Binary Tree General · Module quiz