p15 Symmetric — Progressive Hints

Rule: ONE hint at a time, 5-min timer.

Hint 1 — Reframe

A tree is symmetric iff its left subtree is the MIRROR of its right subtree. Mirror of what we did in p13 (Same Tree). What changes from “same” to “mirror”?

Hint 2 — The pairing

In Same Tree we paired children straight: (a.left, b.left) and (a.right, b.right). For mirror, we pair them crossed: (a.left, b.right) and (a.right, b.left). That’s the entire algorithmic difference.

Hint 3 — Base cases

Same four cases as p13:

  • Both None → True
  • One None → False
  • Values differ → False
  • Both non-None, values equal → recurse on cross-paired children, AND the results.

Hint 4 — Pseudocode

def is_mirror(a, b):
    if a is None and b is None: return True
    if a is None or b is None: return False
    return a.val == b.val \
       and is_mirror(a.left, b.right) \
       and is_mirror(a.right, b.left)

def is_symmetric(root):
    return root is None or is_mirror(root.left, root.right)

Iterative: single queue of pairs, initialize with (root.left, root.right); on each pop enqueue (a.left, b.right) and (a.right, b.left).

Hint 5 — Full + traps + family

Time O(N), space O(H) recursive or O(W) iterative.

Trap 1 — Forgetting to cross: if you write is_mirror(a.left, b.left), you’re checking that left and right subtrees are IDENTICAL, not mirrors. [1,2,2,3,4,4,3] fails (left subtree [2,3,4], right subtree [2,4,3] — not identical, but ARE mirrors).

Trap 2 — Calling is_same(root, root): always True. Symmetric means mirror of itself, not equal to itself.

Trap 3 — Two separate queues iteratively: desync on None alignment. Single queue of pairs.

The fixed-point insight: T is symmetric iff invert(T) == T. From p11 we know invert is involutive: invert(invert(T)) == T. From p15 we know symmetric trees are the fixed points of invert. Alternative implementation: is_same(T, invert(T)) (uses p11 + p13). Direct mirror-walk is cleaner.

Family:

  • LC 100 — Same Tree (p13): straight-pair.
  • LC 951 — Flip-Equivalent: (straight) OR (cross) at each node. 2^N naive; O(N) with structural canonicalization.
  • N-ary symmetric: children list is a palindrome of mirror-subtrees.

Same skeleton, different pairing. Pattern reuse is the lesson.