Monday, August 3, 2015

Mirror image of a binary tree

Given a binary tree, how to convert it to it's mirror image?
For example consider the following binary tree and it's mirror image.
Here simply, the left and right sub trees of each node are inverted. So we have to simply invert the given binary tree. It is a simple implementation problem. Using recursion we can solve it by following the below steps
  1. If root is NULL, simply return
  2. Invert the left sub tree
  3. Invert the right sub tree
  4. Swap left and right sub trees.
Here is the C++ code which implements the above algorithm. It runs in O(n) time.