Symmetric Tree

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

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)

Two trees are mirrors if:

• Their roots have equal values.
• Left subtree of one is a mirror of the right subtree of the other.

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

• Invariant: isMirror(a,b) checks symmetry of two subtrees.
• Base cases handle nil/leaf nodes correctly.
• Recursive calls return correct results for subtrees (induction).
• Combining subtree results yields the correct answer for the current node.

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.

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.