Invert Binary Tree in DAA
Invert Binary Tree: A binary tree is a tree in which each node of the tree contains two children, i.e., left children and right children. Let us suppose we have given a binary tree, and the task is to invert the given binary tree. Inverting a Tree will create the mirror of it.
For Example:
Input:
Output:
Explanation: Inverting the given binary tree will flip all the nodes as a mirror image.
The approach used in the below program to solve this problem is as follows:
Inverting a binary tree is also known as the mirroring of the given tree, but to invert a binary tree, we will create a temporary node that will keep the nodes in each level and swap the left node as well as a right node.
- Take input nodes of the binary Tree.
- A function flipNode(node*root) takes the root node as input and helps to create the mirror of the node.
- Swap the left node and right node.
- A function invertBinaryTree(node*root) takes the root node and calls the flipNode(root) function to convert a binary tree in its invert form.
Example:
#include<iostream> using namespace std;
struct treenode
{
int data;
treenode*left;
treenode*right;
};
struct treenode* createNode(int d)
{
struct treenode*root= new treenode;
root->data= d; root->left= NULL; root->right= NULL; return root;
}
void flipNodes(treenode*root)
{
if(root==NULL)
{
return;
}
treenode*temp= root->left; root->left= root->right; root->right= temp;
}
treenode*invertBinaryTree(treenode*root)
{
flipNodes(root); return root;
}
int heightofTree(treenode*root)
{
if(root==NULL)
{
return 0;
}
return max(heightofTree(root->left), heightofTree(root->right))+1;
}
void givenlevel(treenode*root, int lev)
{
if(root==NULL)
{
return;
}
if(lev==1)
{
cout<<root->data<<" ";
}
else if(lev>1)
{
givenlevel(root->left,lev-1);
givenlevel(root->right,lev-1);
}
}
void printLevelwise(treenode*root)
{
int height= heightofTree(root);
int i; for(i=1;i<=height;i++)
{
givenlevel(root,i);
}
}
int main()
{
struct treenode*root= NULL;
root= createNode(4);
root->left= createNode(2);
root->right= createNode(7);
root->left->right= createNode(3);
root->left->left= createNode(1);
root->right->left= createNode(6);
root->right->right= createNode(9);
printLevelwise(root);
cout<<"After Inverting:"<<endl; invertBinaryTree(root);
printLevelwise(root);
return 0; }
Running the above code will generate the output as follows:
Output:
4 2 7 1 3 6 9 After Inverting: 4 7 2 6 9 1 3