Symmetric Tree

The key to the Symmetric Tree solution is to compare two nodes as a mirror pair, not to traverse the left and right subtrees independently.

Same value, matching empty positions, opposite child direction.

Once that contract is explicit, the algorithm is a small recursive depth-first search.

What the problem is asking

Given the root of a binary tree, determine whether the tree is symmetric around its center. The left and right subtrees must be mirror images.

The supplied constraints allow:

• 1 to 1,000 nodes
• Node values from -100 to 100

Consider this tree:

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

It is symmetric because:

• The two 2 nodes have equal values.
• The outer 3 nodes correspond.
• The inner 4 nodes correspond.
• The left child on one side maps to the right child on the other side.

This tree is also symmetric:

        1
      /   \
     2     2
    /       \
   3         3

The 3 nodes occupy opposite child positions: left on one side and right on the other.

Now compare the near miss:

        1
      /   \
     2     2
    /       /
   3       3

The values match, but both 3 nodes are left children. The shape does not reflect across the center.

That is the central distinction from a Same Tree comparison:

• Same Tree maps left to left and right to right.
• Symmetric Tree maps left to right and right to left.

Recognize the mirror-pair pattern

Do not traverse the two subtrees separately and try to reconstruct their relationship afterward. Carry the relationship in the state.

Define the state as a pair:

(a, b)

where a and b occupy positions that should mirror each other.

For this pair to be valid:

1. Both nodes are missing, or both nodes exist.
2. If both exist, their values are equal.
3. a.left mirrors b.right.
4. a.right mirrors b.left.

The child mapping is the entire problem:

(a.left,  b.right)
(a.right, b.left)

A same-direction comparison would use:

(a.left,  b.left)
(a.right, b.right)

That checks whether two subtrees are equal. It does not check whether they are reflections.

This gives us the recognition cue:

If a tree problem compares two regions under reflection, use paired nodes as the state and cross the child directions.

Why direct structural comparison is better

A tempting baseline is to serialize the left and right subtrees, preserve null markers, reverse one representation, and compare the results.

That approach can be made precise, but it creates extra work. A representation must preserve both node values and empty positions, and the transformation must correctly exchange left-child and right-child positions. Reversing a sequence of tokens alone does not automatically perform that structural transformation.

The tree already exposes the information we need. Compare the two positions directly:

• compare their values,
• compare their crossed children,
• stop at the first mismatch.

The direct approach has fewer moving parts and makes the important rule visible. The baseline is still useful as a thought experiment because it reveals what symmetry depends on: values plus structure, not values alone.

Derive the recursive solution

Create a helper:

is_mirror(a, b)

It returns whether the subtrees rooted at a and b are mirror images.

There are four cases.

Both nodes are missing

If a and b are both None, the two corresponding positions are equally empty:

True

This confirms that the structure matches along that branch.

Exactly one node is missing

If only one node is None, one side contains a subtree and the other does not:

False

This catches structural asymmetry even when every existing value matches.

Both nodes exist with different values

If a.val != b.val, the pair cannot mirror:

False

There is no reason to inspect descendants after the current pair has already failed.

Both nodes exist with equal values

The current pair is valid only if both crossed child pairs are valid:

is_mirror(a.left, b.right)
and
is_mirror(a.right, b.left)

The top-level call compares the root's two children:

is_mirror(root.left, root.right)

The root lies on the center line, so it does not need a second root for comparison.

The recurrence is:

is_mirror(a, b) =
    True,  if a and b are both None
    False, if exactly one is None
    False, if a.val != b.val
    is_mirror(a.left, b.right)
    and is_mirror(a.right, b.left), otherwise

The recursion is not the clever part. Choosing the correct pair state is the important part. Once the state means “these two positions must mirror,” the recursive calls follow directly from that meaning.

Invariant and correctness proof

The invariant is:

Whenever is_mirror(a, b) runs, a and b are the two positions that must reflect each other.

That gives the helper a precise obligation.

If both nodes are None, both mirror positions contain no subtree, so returning True is correct.

If exactly one node is None, one position contains a subtree and the other does not, so returning False is correct.

Now assume both nodes exist. For their subtrees to mirror:

1. Their values must be equal.
2. a.left must mirror b.right.
3. a.right must mirror b.left.

The helper checks the values and recursively checks exactly those two crossed pairs. If both recursive calls return True, every required part of the current pair matches.

Each recursive call moves into smaller subtrees. Eventually, every corresponding position either reaches a matching pair of empty positions or exposes a missing node, a mismatched value, or a deeper structural mismatch. Therefore, the algorithm returns True exactly when the tree is symmetric.

Correctness condition: equal values are necessary, but they are not sufficient. The null positions must mirror too.

The most common bug is writing same-direction recursion:

is_mirror(a.left, b.left)
is_mirror(a.right, b.right)

That compares the subtrees in the same orientation. Write the mapping before writing the code:

left  → right
right → left

This prevents the central mistake at its source.

Dry run: follow the mirror pairs

Use the symmetric tree:

        1
      /   \
     2     2
    / \   / \
   3   4 4   3

The initial pair is (2, 2):

Pair	Current values	Crossed child pairs	Result
(2, 2)	Equal	(3, 3), (4, 4)	Depends on both
(3, 3)	Equal	(None, None), (None, None)	True
(4, 4)	Equal	(None, None), (None, None)	True
(2, 2)	Equal; both child pairs pass	—	True

The (None, None) calls are meaningful. They confirm that both corresponding positions are empty.

Now trace the near miss:

        1
      /   \
     2     2
    /       /
   3       3

Start with (2, 2). Their values match.

The crossed child pairs are:

(a.left,  b.right) = (3, None)
(a.right, b.left)  = (None, 3)

The first pair contains one node and one missing position, so it returns False. Matching values cannot rescue a mismatched shape.

When debugging this problem, write down the current pair and then write its two crossed child pairs. If that pair table is wrong, the implementation will be wrong too.

Symmetric Tree solution in Python

from typing import Optional


class Solution:
    def isSymmetric(self, root: Optional["TreeNode"]) -> bool:
        def is_mirror(
            a: Optional["TreeNode"],
            b: Optional["TreeNode"],
        ) -> bool:
            # Both mirror positions are empty.
            if a is None and b is None:
                return True

            # Exactly one mirror position is empty.
            if a is None or b is None:
                return False

            # Existing nodes must have equal values.
            if a.val != b.val:
                return False

            # Compare children in opposite directions.
            return (
                is_mirror(a.left, b.right)
                and is_mirror(a.right, b.left)
            )

        # The contract contains at least one node. This guard
        # defensively handles a null root as well.
        if root is None:
            return True

        return is_mirror(root.left, root.right)

Each branch maps directly to a problem obligation:

• Both None accepts matching empty structure.
• Exactly one None rejects different shapes.
• Different values reject unequal nodes.
• Crossed child arguments enforce reflection.

Python's and operator short-circuits. If the first crossed comparison fails, the second is not evaluated. That can avoid unnecessary work, but short-circuiting is not the proof of correctness. The algorithm is correct because both crossed relationships are required.

My interview checklist is:

1. Handle both-null and one-null pairs.
2. Compare the current values.
3. Cross the child directions.
4. Start with the root's left and right children.

If you remember only “compare two trees recursively,” you can still write the wrong solution. If you remember the pair contract, the code becomes almost mechanical.

Complexity and edge cases

Let n be the number of nodes and h be the tree height.

Time complexity

The time complexity is O(n).

Each node is examined at most once as part of a mirror pair, and each pair requires constant work apart from its recursive calls.

Space complexity

The recursive call stack uses O(h) auxiliary space.

For a balanced tree, h is smaller than n. For a skewed tree, h can equal n, so the worst-case auxiliary space is O(n).

An iterative version would store pending mirror pairs in an explicit stack or queue. It has the same linear-time bound and may be useful when recursion depth is a concern, but recursion is the clearest primary implementation because its state directly matches the definition of a mirror pair.

Edge cases within the contract

Case	Expected result	What it checks
Single-node tree	True	No opposing subtree
Two equal leaf children	True	Basic value match
Different root-side values	False	Immediate value failure
Mirrored child positions	True	Crossed mapping
Same-side children	False	Null-structure checking
One child missing on one side	False	One-null base case
Deeper mismatch	False	Failure propagation

The contract requires at least one node, so an empty tree is outside the stated input range. The implementation still returns True for root is None as defensive behavior: there is no structure that breaks symmetry.

The two cases that expose most bugs are:

(None, node)
(node, None)

and the difference between:

(a.left, b.right)

and:

(a.left, b.left)

Test both deliberately. A perfectly symmetric example proves only that the happy path works.

The transferable pattern

When a tree problem asks whether two regions correspond under reflection, use a pair of nodes as the DFS state.

Then define the contract before writing traversal code:

• equal values,
• matching null structure,
• crossed children.

That is the durable Symmetric Tree solution. Do not memorize the recursive function as a block of Python. Trace one symmetric tree and one near miss by writing down the mirror pairs.

Pair first. Map the children. Then code. Once the relationship is visible, the recursion is no longer a trick—it is the direct expression of the structure.