Saturday, May 9, 2015

Check if a binary tree is the mirror image of itself

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.
  1. An empty tree is a symmetric tree.
  2. At each node we check the following
    1. If the left value and right value are same
    2. If the left sub-tree of left node and right sub-tree of the right node are mirror images
    3. If the right sub-tree of left node and left sub-tree of the right node are mirror images
  3. If all the above conditions are satisfied then the tree is symmetric.
Here is the C++ implementation of this.