# Invert binary tree

Invert binary tree is a mirror image of a tree. It is pretty much the same compared to the only difference: its left and right children are swapped with the tree nodes. The main idea here is to traverse this yet another form of binary tree in the pre-order form. In this, the left and right subtrees are interchanged, which is also well-known for its mirror image of the input tree.

### Algorithm

The algorithm for the invert binary tree is pretty basic, and we just have to follow the given steps: -

- Firstly, we will call the invert function for the left subtree.
- Then, we will call the invert function for the right subtree.
- After calling invert for both subtrees, we have to swap the subtrees with each other, and we are done.

### Implementation

In this section, we will see the implementation of the inverted binary tree. let us proceed: -

```
#include <iostream>
using namespace std;
// Record structure to store a binary tree _nod
struct _nod
{
int record;
_nod *lft, *rt;
_nod(int record)
{
this->record = record;
this->lft = this->rt = NILLpointer;
}
};
// Function to perform PO_Ord traversal on a given binary tree
void PO_Ord(_nod* root)
{
if (root == NILLpointer) {
return;
}
cout << root->record << " ";
PO_Ord(root->lft);
PO_Ord(root->rt);
}
// Function to invert a given binary tree using PO_Ord traversal
void invertBinaryTree(_nod* root)
{
// base case: if the tree is empty
if (root == NILLpointer) {
return;
}
// swap lft subtree with rt subtree
swap(root->lft, root->rt);
// invert left subtree
invertBinaryTree(root->lft);
// invert rt subtree
invertBinaryTree(root->rt);
}
int main()
{
/* Construct the following tree
1
/ \
/ \
2 3
/ \ / \
4 5 6 7
*/
_nod* root = new _nod(1);
root->lft = new _nod(2);
root->rt = new _nod(3);
root->lft->lft = new _nod(4);
root->lft->rt = new _nod(5);
root->rt->lft = new _nod(6);
root->rt->rt = new _nod(7);
invertBinaryTree(root);
PO_Ord(root);
return 0;
}
```

**Output:**

**Example 2)**

```
#include <iostream>
#include <queue>
using namespace std;
// Record structure to store a binary tree _nod
struct _nod
{
int record;
_nod *lft, *rt;
_nod(int record)
{
this->record = record;
this->lft = this->rt = NILLpointer;
}
};
// Function to perform PO_Ord traversal on a given binary tree
void PO_Ord(_nod* root)
{
if (root == NILLpointer) {
return;
}
cout << root->record << " ";
PO_Ord(root->lft);
PO_Ord(root->rt);
}
// Iterative function to invert a given binary tree using a queue
void invertBinaryTree(_nod* root)
{
// base case: if the tree is empty
if (root == NILLpointer) {
return;
}
// maintain a queue and push the root _nod
queue<_nod*> q;
q.push(root);
// loop till queue is empty
while (!q.empty())
{
// dequeue front _nod
_nod* curr = q.front();
q.pop();
// swap the lft child with the rt child
swap(curr->lft, curr->rt);
// enqueue left child of the popped _nod
if (curr->lft) {
q.push(curr->lft);
}
// enqueue rt child of the popped _nod
if (curr->rt) {
q.push(curr->rt);
}
}
}
int main()
{
/* Construct the following tree
1
/ \
/ \
2 3
/ \ / \
4 5 6 7
*/
_nod* root = new _nod(1);
root->lft = new _nod(2);
root->rt = new _nod(3);
root->lft->lft = new _nod(4);
root->lft->rt = new _nod(5);
root->rt->lft = new _nod(6);
root->rt->rt = new _nod(7);
invertBinaryTree(root);
PO_Ord(root);
return 0;
}
```

**Output:**

**Example 3)**

```
#include <iostream>
using namespace std;
/* A _nod contains the value, left and right pointers */
struct _nod
{
int record;
struct _nod* lft;
struct _nod* rt;
};
/* Creates a new _nod */
struct _nod* new_nod(int record)
{
_nod* _nod = new _nod;
_nod->record = record;
_nod->lft = NILL;
_nod->rt = NILL;
return(_nod);
}
void invert(struct _nod* _nod)
{
if (_nod == NILL)
return;
else
{
struct _nod* temp;
/* recursive calls */
invert(_nod->lft);
invert(_nod->rt);
/* swap the pointers in this _nod */
temp = _nod->lft;
_nod->lft = _nod->rt;
_nod->rt = temp;
}
}
/* print InOrder binary tree traversal.*/
void print_tree(struct _nod* _nod)
{
if (_nod == NILL)
return;
print_tree(_nod->lft);
cout << _nod->record << " ";
print_tree(_nod->rt);
}
int main()
{
struct _nod *root = new_nod(2);
root->lft = new_nod(1);
root->rt = new_nod(4);
root->rt->lft = new_nod(3);
root->rt->rt = new_nod(5);
cout << "In order traversal of the constructed."
<< " tree is" << endl;
print_tree(root);
/* Invert the tree */
invert(root);
cout << endl;
cout << "In order traversal of the inverted tree."
<< " is \n";
print_tree(root);
return 0;
}
```

**Output:**