Convert binary tree to its mirror

Given a binary tree, write an efficient algorithm to convert binary tree to its mirror.

 

For example, below binary trees are mirror of each other.


                  |          
         1        |        1 
       /   \      |      /   \
      2     3     |     3     2
     / \   / \    |    / \   / \
    4   5 6   7   |   7   6 5   4
                  |

 


 

The idea is very simple. We traverse the tree in postorder fashion and for every node we swap its left and right child pointer after recursively converting its left subtree and right subtree first to mirror. Below is the C++ implementation of the idea –

C++

Download   Run Complete Code

The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

 

 
 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz