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.
2 2 Symmetric
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.