Reference: LeetCode EPI 9.2
Difficulty: Easy

Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Example:

[1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Follow up: Bonus points if you could solve it both recursively and iteratively.

Analysis

Idea: A tree is symmetric if it is a mirror reflection of itself.

Note: Distinguish the concept of symmetric (one tree) and mirror reflection (two trees).

The question is when are two trees a mirror reflection of each other? Three conditions:

• Their two roots have the same value.
• The right subtree t1.right of each tree t1 is a mirror reflection of the left subtree t2.left of the other tree t2.
• The left subtree t1.left of each tree t1 is a mirror reflection of the right subtree t2.right of the other tree t2.

Bad Idea (the wrong direction):

A tree is symmetric if its left subtree is symmetric and its right subtree is symmetric. Consider this case:

Two subtrees of root are not symmetric, but the root is symmetric.

From EPI, swapping any subtrees of a tree and comparing with the original is also workable.

Recursion

Come up with the recursive structure.

Improvement:

Actually, there is not too much improvement since it is bounded by a constant $2$.

Time: $O(N)$ because we traverse the entire input tree once ($\sim 2N$).
Space: $O(h)$

Iteration (One/Two Stacks)

Use two stacks to simulate the recursive method.

Note: Null check => Value check

Or just use one stack:

• Be careful of the ordering of pushing.

Time: $O(N)$
Space: $O(h)$

Iteration (BFS)

Compare nodes at each layer.

• Each two consecutive nodes in the queue should be equal.
• Each time, two nodes are extracted and their values are compared.
• Then their right and left children of the two nodes are enqueued in opposite order.

Time: $O(N)$
Space: $O(w)$ where $w$ is the maximum number nodes in a level of the tree.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.