# 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: -

1. Firstly, we will call the invert function for the left subtree.
2. Then, we will call the invert function for the right subtree.
3. 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: