Given a binary tree, how do we write a program to check if it is the mirror image of itself. This binary tree is also called a symmetric tree.

A binary tree is called a symmetric tree if it’s left and right sub-trees are mirror images of each other.

For example Let us consider the following examples of some symmetric and asymmetric trees.

1 / Symmetric 2 2 |
1 / Asymmetric 2 3 |
1 / 2 2 Symmetric / 3 3 |

We can design a recursive algorithm like the following.

- An empty tree is a symmetric tree.
- At each node we check the following
- If the left value and right value are same
- If the left sub-tree of left node and right sub-tree of the right node are mirror images
- If the right sub-tree of left node and left sub-tree of the right node are mirror images
- If all the above conditions are satisfied then the tree is symmetric.

Here is the C++ implementation of this.