101. Symmetric Tree

101

EasyTrees and Binary Search TreesDFS comparing outer/inner childrenMirror recursion on paired children

Symmetric Tree

Given the root of a binary tree, return true if the tree is a mirror image of itself around its center, i.e. symmetric.

In plain English

Determine whether a binary tree looks the same when reflected left-to-right about its root.

Picture it like this

Fold the tree down the middle like a paper butterfly: it is symmetric if the left wing lands exactly on the right wing, node for node.

Example

Input: root = [1, 2, 2, 3, 4, 4, 3]
Output: true
Why: The left subtree (2,3,4) is the mirror of the right subtree (2,4,3), so the whole tree reflects onto itself.

Constraints

The number of nodes is in the range [1, 1000]-100 <= Node.val <= 100

Pattern lesson

See the pattern, then code

Mirror recursion on paired children

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Symmetry is same-tree comparison with a twist: the left child of one side must equal the RIGHT child of the other. Compare (a.left, b.right) and (a.right, b.left).

New words, made simpleKnow these before the algorithm

Mirror image: The tree obtained by swapping every node's left and right children.
Outer pair: The far-apart children (left's left with right's right).
Inner pair: The close-together children (left's right with right's left).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Invert half and compare

Correct but wastes memory building a reversed copy.

Build the mirror of the right subtree, then run same-tree against the left.

Time O(n)Space O(n)

Best choiceCross-wise recursion

No extra structure; the reflection is baked into the recursion order.

Directly compare (left.left, right.right) and (left.right, right.left).

Time O(n)Space O(h)

The rule we keep true

Invariant

mirror(a, b) returns true exactly when the subtree at a is the mirror reflection of the subtree at b.

Why this is correct

Reasoning

Two subtrees are mirror images iff their roots have equal values and a's left reflects b's right while a's right reflects b's left. The recursion checks precisely this at every level, so by induction the whole tree is symmetric iff mirror(root.left, root.right) holds.

The algorithm in three movesSay these aloud before coding

1Handle empty tree as symmetric

mirror(2,2): equal

2Compare the two subtrees a and b: both null -> match

mirror(3,3) [outer]: equal

3One null or values differ -> mismatch

mirror(4,4) [inner]: equal -> true

4Recurse cross-wise: a.left with b.right and a.right with b.left

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readroot.left=2, root.right=2

2 · Askvalues equal?

3 · Update state2 == 2

4 · Resultrecurse cross-wise

Key takeaway

Outer pair (3,3) and inner pair (4,4) reflect across the center.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Both null
Two absent subtrees mirror each other trivially.
2
Lines 5-6Mismatch
One side missing or unequal values breaks symmetry.
3
Lines 7Cross recursion
The reflection is enforced by pairing a.left with b.right and a.right with b.left.
4
Lines 9Kick off
Compare the root's two subtrees; an empty tree is symmetric.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single node -> true
Same values but asymmetric shape (e.g. [1,2,2,null,3,null,3]) -> false
Empty tree -> true

Common beginner mistakes

Comparing left.left with right.left (same-tree logic) instead of the cross pairs
Accessing .val before null checks
Comparing the root against itself instead of its two children

Check your understanding

How does symmetric-tree recursion differ from same-tree recursion?

Symmetric Tree

Symmetric Tree

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees