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.
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
- If root is NULL, simply return
- Invert the left sub tree
- Invert the right sub tree
- Swap left and right sub trees.
Here is the C++ code which implements the above algorithm. It runs in O(n) time.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| //Binary tree node type | |
| struct TreeNode | |
| { | |
| int val; | |
| TreeNode *left, *right; | |
| TreeNode(int v):val(v),left(NULL), right(NULL){} | |
| }; | |
| TreeNode* invert(TreeNode *root) | |
| { | |
| if(root == NULL) | |
| return root; | |
| root->left = invert(root->left); | |
| root->right = invert(root->right); | |
| TreeNode *temp = root->left; | |
| root->left = root->right; | |
| root->right = temp; | |
| return root; | |
| } | |
| void print_level_order(TreeNode *root) | |
| { | |
| if( root == NULL ) | |
| return; | |
| queue<TreeNode *> q; | |
| q.push(root); | |
| while( !q.empty()) | |
| { | |
| TreeNode *temp = q.front(); | |
| q.pop(); | |
| cout << temp->val << " "; | |
| if( temp->left ) | |
| q.push(temp->left); | |
| if( temp->right ) | |
| q.push(temp->right); | |
| } | |
| } | |
| void Test() | |
| { | |
| TreeNode *root = new TreeNode(1); | |
| root->left = new TreeNode(2); | |
| root->right = new TreeNode(3); | |
| root = invert(root); | |
| print_level_order(root); | |
| } | |
| int main() | |
| { | |
| Test(); | |
| return 0; | |
| } |
by