Binary Tree Inversion

 This is a special article to show you how to invert a binary tree. A binary tree is a data structure where data types (integers, floats, strings) are stored in a tree. This tree as the name suggests has two children: Left child and Right child and a root node at the top of the tree. Normally, left child is stored at the left side of a node and the right child at the right side of the node.

Look at the image: 

Google image

To design an algorithm for a binary tree is easy. I am going to focus on how to get its mirror image once you have created a binary tree.

Algorithm to create mirror image of binary tree

Once you have created a binary tree, you get a root node of this tree.

What is the difference(s) between normal binary tree and its mirror image?

Ans: In a binary tree, for a parent node, its children have swapped their positions, i.e , left child became right child and vice-versa to become inverted binary tree. Root node stays at the same position.

Algorithm:

Step1. Start traversing the tree until you get the null node

           (Either start from left child or right child)

Step2. Once you get null node, return and swap your left and right child.

              And Voila, It's done!!!

Code:

---

#include <iostream>

using namespace std;

class bt{

      public:

bt* root;

bt* left;

bt* right;

int data;

        // utility function to create a binary tree.

bt* add(int x, bt* root){

if(root==NULL){

bt* nd=new bt();

nd->data=x;

nd->left=NULL;

nd->right=NULL;

root=nd;

return root;

}

else if(x<root->data){

root->left=add(x, root->left);

}else{

root->right=add(x, root->right);

}

return root;

}

void print(bt* r){

if(r==NULL){

return;

}

print(r->left);

cout << r->data << endl;

print(r->right);

}

       

        // utility function to invert a binary tree

bt* invert(bt* r){

if(r==NULL){

return r;

}

bt* t=invert(r->left);

r->left=invert(r->right);

r->right=t;

return r;

}

};

int main(){

int a[]={10, 7, 11};

int n=sizeof(a)/sizeof(int);

bt* b=new bt();

b->root=NULL;

for(int i=0;i<n;i++){

b->root=b->add(a[i], b->root);

}

cout << "normal binary tree: " << endl;

b->print(b->root);

cout << "inverted binary tree: " << endl;

bt* root1=NULL;

root1=b->invert(b->root);

b->print(root1);

return 0;

}

---

If anything missed, please let me know.

Image source: Google image.

Reference:

Binary tree