Reference: LeetCode EPI 9.2

Difficulty: Easy

My Post: [isMirror] DFS (Recursion, One/Two Stacks) + BFS (Queue) Solution in Java

## 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:

1 | 1 |

But the following `[1,2,2,null,3,null,3]`

is not:

1 | 1 |

**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).

1 | 1 |

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:

1 | 1 |

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.

1 | public boolean isSymmetric(TreeNode root) { |

**Improvement:**

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

1 | public boolean isSymmetric(TreeNode root) { |

**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

1 | public boolean isSymmetric(TreeNode root) { |

Or just use one stack:

- Be careful of the ordering of pushing.

1 | public boolean isSymmetric(TreeNode root) { |

**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.

1 | 1 |

1 | public boolean isSymmetric(TreeNode root) { |

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