p15 — Symmetric Tree

Source: LeetCode 101 · Easy · Topics: Tree, DFS, BFS Companies (2024–2025 frequency): Meta (high — paired with LC 100), Amazon (high), Microsoft (high), Bloomberg (medium), Google (medium), Apple (medium) Loop position: phone screen; canonical “compare a tree against its mirror” — direct application of p13 with cross-pairing.

1. Quick Context

This is the mirror-walk generalization of p13 (Same Tree). Instead of comparing two separate trees with straight pairing (a.left ↔ b.left, a.right ↔ b.right), we compare a tree against itself with cross pairing (a.left ↔ b.right, a.right ↔ b.left). That single change in pairing IS the mirror operator.

Mastering this unlocks LC 951 (Flip-Equivalent — pair-OR-cross-pair allowed), LC 572 (Subtree — uses LC 100 as a sub-routine), LC 1367 (Linked-list-in-tree), and the entire “tree-shape-matching” family. It also reinforces the lesson from p13: the recursion structure stays the same; only the pairing changes.

Mid candidates write the recursion. Senior candidates write it cold AND the iterative BFS-pairs version. Staff candidates connect it to LC 951 (“now ALSO match if you cross-pair OR straight-pair at any node — the equivalence has a choice at each level”) and explain why that variant is harder (2^N branching without memoization, or O(N) with structural-hash memoization).

What it looks like it tests: is this tree a mirror of itself? What it actually tests: can you recognize that mirror-walk = parallel-walk with cross-pairing? Do you generalize patterns, or memorize problems?

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/symmetric-tree/

STOP. 5-min timer. Recursive AND iterative.

3. Prerequisite Concepts

  • p13 — Same Tree (the four-case parallel-walk template)
  • Mirror/reflection as a tree operation (invert from p11)
  • Paired iteration with single queue

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Given the root of a binary tree, return True iff the tree is a mirror image of itself — i.e., the left subtree is a mirror image of the right subtree (and recursively).”

Step 2 — Clarify:

  • “Empty tree — symmetric?” (Yes, vacuously.)
  • “Single node?” (Yes.)
  • “Different values at mirror positions?” (Not symmetric.)
  • “Structure must match too, right?” (Yes — [1,2,null] and [1,null,2] would be symmetric; [1,2] alone isn’t.)

Step 3 — Constraints: N up to 1000 (LC). O(N) achievable.

Step 4 — Examples:

  • [1,2,2,3,4,4,3] → True.
  • [1,2,2,null,3,null,3] → False (mirror positions differ structurally).
  • [1] → True.
  • [1,2,2] → True.
  • [1,2,3] → False (values differ at mirror positions).

Step 5 — Brute Force: Build the mirror image (use invert from p11), then compare to original with is_same (p13). O(N) time, O(N) space (constructed mirror). Works. The direct mirror-walk is the same time complexity but O(H) space.

Step 6 — Complexity: O(N) time, O(H) recursive or O(W) iterative.

Step 7 — Pattern Recognition: “Compare tree against its mirror” → parallel-walk with cross-pairing.

Step 8 — Optimize: The mirror-walk version skips the intermediate construction; same asymptotic but constant-factor better and cleaner.

Step 9 — Prove correctness: A tree T is symmetric iff for every “mirror-paired” node pair (a, b) (where a is at position p in T, and b is at the mirror-position of p), values match AND mirror-paired children match. Mirror pair (a.left, b.right) and (a.right, b.left). By induction on combined subtree size, the recurrence returns True iff all mirror-pairs match.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Same Algorithm, Cross-Pairing

The crucial reframe. Don’t think of LC 101 as a new problem. Think:

“LC 101 is LC 100 (Same Tree) applied to (root.left, root.right) with the recursion’s RECURSIVE PAIRING changed from straight to cross.”

Same Tree:

def is_same(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_same(a.left,  b.left) \
       and is_same(a.right, b.right)

Mirror (Symmetric helper):

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) \   # CROSS
       and is_mirror(a.right, b.left)      # CROSS

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

Three lines change: pairing the children diagonally. THAT is the mirror operator expressed as recursion structure.

Why this generalizes — LC 951 (Flip-Equivalent): “Two trees are flip-equivalent if we can turn one into the other by flipping (swapping left↔right) any subset of nodes.” Recurrence:

def flip_equiv(a, b):
    if a is None and b is None: return True
    if a is None or b is None or a.val != b.val: return False
    # At each node we can CHOOSE: match straight OR cross-pair.
    return (flip_equiv(a.left, b.left) and flip_equiv(a.right, b.right)) \
        or (flip_equiv(a.left, b.right) and flip_equiv(a.right, b.left))

The OR introduces branching — naive is 2^N. With structural-hash canonicalization (recursively canonicalize each subtree to a hash with a deterministic ordering), it’s O(N). Recognize that LC 951’s exponential blow-up comes from the OR; mention canonicalization as the fix.

Iterative form: single queue of pairs (a, b) initialized with (root.left, root.right). Pop, check both-None/one-None/val-mismatch, then enqueue (a.left, b.right) and (a.right, b.left). Same as p13 with cross-pairing.

Why the iterative version matters for interviews: if asked “iteratively” mid-flow, a Senior should write it in <5 min without restarting from scratch — just copy the parallel-walk-iterative from memory and apply cross-pairing.

The mirror-as-relation insight: “Symmetric tree” is the FIXED POINT of the invert operation: invert(T) == T. From p11 we know invert(invert(T)) == T is the involution. From LC 101 we now know invert(T) == T iff T is symmetric. So we have two ways to test symmetry:

  1. Direct: mirror-walk (this problem).
  2. Indirect: compute invert(T) (p11), compare with is_same(T, invert(T)) (p13). Same complexity, uses two earlier primitives.

State both; the direct is cleaner.

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Comparing tree to itself with straight pairing:

def is_symmetric(root):
    return is_same(root, root)

Always True. Symmetric means mirror, not identical-to-itself. Trivially wrong but a real first attempt.

Wrong-but-tempting #2 — Forgetting to cross:

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.left) and is_mirror(a.right, b.right)

This is is_same(a, b) — checks if left and right subtrees are IDENTICAL, not mirrors. [1, 2, 2, 3, 4, 4, 3] would fail (left subtree [2,3,4], right subtree [2,4,3] — not identical but ARE mirrors).

Wrong-but-tempting #3 — Reverse only one level:

def is_symmetric(root):
    if root is None: return True
    return root.left.val == root.right.val

Only checks top-level values. Misses deeper asymmetries.

Wrong-but-tempting #4 — Iterative with naive two-queue desync (same as p13 mistake): Two separate queues lose track of None alignment. Use ONE queue of pairs.

Wrong-but-tempting #5 — Conflating “structurally symmetric” with “all values equal”:

def is_symmetric(root):
    # gather all values; check palindrome

Tree shape isn’t a linear sequence; flattening loses structural info. Don’t try clever sequence tricks.

8. Skills & Takeaways

Generalizable patterns:

  • Cross-pairing recursion — same skeleton as parallel-walk, different pair argument.
  • Reuse-by-reframing — recognize new problems as existing patterns with a twist.
  • Fixed-point insight — symmetric = invert(T) == T.

Analogous problems:

  • LC 100 — Same Tree (p13): straight-pairing.
  • LC 951 — Flip-Equivalent: OR-of-(straight, cross).
  • LC 572 — Subtree of Another Tree.
  • LC 226 — Invert Binary Tree (p11): the operator we’re testing fixed-point of.
  • LC 110 — Balanced Binary Tree: structural property checked recursively.

When NOT to use mirror-walk: if you’ve already inverted the tree for another reason and have the inverted version handy, is_same(T, inverted_T) is simpler.

9. When to Move On

  • I write is_mirror in <3 min, with cross-pairing reflex.
  • I write iterative version (single queue of pairs) in <5 min.
  • I articulate “symmetric = invert(T) == T” and show two solution paths.
  • My stress_test() randomly mirrors a tree (build random + clone + invert) and asserts symmetric.
  • I sketched LC 951 (Flip-Equivalent) and identified the 2^N blow-up + canonicalization fix.

10. Company Context

Meta (chained with LC 100)

  • The framing: “Are these two trees identical?” → “Now check symmetric.”
  • What they want to hear: “Same algorithm, cross-pair the children.” Speed of pivot signals pattern-recognition.

Amazon

  • The framing: Sometimes “balanced UI layout: check that this binary widget tree is left-right symmetric.”
  • What they want to hear: Direct mirror-walk + iterative variant.

Microsoft / Apple / Bloomberg / Google

  • Standard problem. Clean recursion + iterative on request.
  • Google adversarial: “Now check Flip-Equivalent (LC 951). What’s the time complexity?” (2^N naive; O(N) with canonicalization.)

11. Interviewer’s Lens

PhaseStrongWeakScorecard (strong)
Reading“Empty? Single? Just values or structure too?”Dives“Clarifies symmetry definition”
Approach“Same as LC 100 with cross-pair.”“Hmm, let me think…”“Recognizes pattern reuse — Senior”
CodingAll four base cases + cross-pair in <3 minForgets cross OR misses null case“Reflex mirror-walk”
IterativeSingle queue of pairs in <5 minRestarts thinking“Knows iterative parallel pattern”
LC 951 pivotNames OR-branching + canonicalizationConfused by “flip”“Sees the family — Staff”

12. Level Delta

LevelLooks like
MidRecursive after one debug. ~6 min.
SeniorRecursive cold + iterative on request. Names “same as LC 100 with cross-pair.” ~5 min.
StaffSenior + LC 951 sketch in <5 min + canonicalization mention.
PrincipalStaff + production framing (UI layout symmetry checks, image-symmetry detection, palindromic-structure detection in DOM/AST trees).

13. Follow-up Questions

Follow-up 1: “Iteratively.”

“Single queue of pairs. Initialize [(root.left, root.right)]. Pop pair (a, b); both-None → continue; one-None or val-mismatch → False; enqueue (a.left, b.right) and (a.right, b.left). O(N), O(W).”

Follow-up 2: “What’s the relationship to LC 226 (Invert Tree)?”

“T is symmetric iff invert(T) == T. Symmetric trees are the fixed points of the invert operation. Alternative implementation: is_same(T, invert(T)) — works, slower by constant factor due to building the inverted tree.”

Follow-up 3: “Now LC 951 — Flip-Equivalent.”

“Same skeleton; the recurrence ORs straight-pair AND cross-pair: flip_equiv(a, b) = match_with_value AND ((flip_equiv(a.left, b.left) AND flip_equiv(a.right, b.right)) OR (flip_equiv(a.left, b.right) AND flip_equiv(a.right, b.left))). Naive is 2^N due to OR branching. Optimal: canonicalize each subtree by sorting children’s structural hashes; then flip_equiv reduces to canonical(a) == canonical(b). O(N log N) for the canonicalization sort, or O(N) average with hashing.”

Follow-up 4: “What about an N-ary tree symmetric version?”

“Define: a node is N-ary-symmetric if its children list is a palindrome of children-subtrees (with mirror-recursion). So compare child[0] with child[N-1] mirror-wise, child[1] with child[N-2], etc. Skip the middle for odd N. Same template; loop over child pairs.”

Follow-up 5 (Principal signal): “Where does this matter in production?”

“DOM-tree symmetry checks for UI testing (visual regression frameworks: ‘is this rendered layout symmetric per the design spec?’). Image-symmetry detection (after building a quadtree, check left-right and top-bottom mirror). Code-formatter / AST-balance checks. In all cases, the tree is large; iterative variant is mandatory.”

14. Full Solution Walkthrough

See solution.py. Five sections:

  1. TreeNode + helpers (build_tree, random_symmetric_tree)
  2. is_symmetric_recursive (mirror-walk)
  3. is_symmetric_iterative (single queue of pairs)
  4. is_symmetric_via_invert (reuses invert and is_same)
  5. stress_test — random symmetric trees expect True; perturbed expect False; three implementations agree
  6. edge_cases — empty, single, two-node, classic [1,2,2,3,4,4,3], asymmetric perturbations

15. Beyond the Problem — Production Reality

Applications:

  • UI layout symmetry verification (design systems, visual regression).
  • AST-balance / formatter sanity (parens, braces).
  • Image symmetry (after quadtree decomposition).
  • Decision-tree pruning (symmetric subtrees can be deduplicated).
  • Game theory (symmetric game-trees admit identical optimal play on mirrored positions; engines exploit symmetry to prune search).

Production caveat: real-world “approximate” symmetry needs a tolerance threshold (allow K mismatches). The recursion becomes “count mismatches; accept if ≤ K.” Same skeleton, different aggregation.

Principal-engineer code review comment: “For our design-system layout validator, the strict-symmetric check rejected too many almost-symmetric layouts (off-by-1px or accent-color differences). We generalized to is_mirror_with_tolerance(a, b, tol) — same recursion, with abs(a.val - b.val) <= tol instead of a.val == b.val AND a global mismatch-count budget. Lesson: the recursion structure is reusable across all ‘compare-two-things’ problems; only the leaf-comparison and aggregation policies change.”