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.

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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Function to perform pre-order traversal of the binary tree void preorder(Node* root) { if (root == nullptr) return; cout << root->data << " "; preorder(root->left); preorder(root->right); } // Function to convert given binary Tree to its mirror bool convertToMirror(Node *root) { // base case: if tree is empty if (root == nullptr) return true; // convert left subtree convertToMirror(root->left); // convert right subtree convertToMirror(root->right); // swap left subtree with right subtree swap(root->left, root->right); } |

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