Mirror of a Binary Tree in C++
In this tutorial, we will learn about how to build a mirror of the binary tree in C++.
We will also see examples to understand the concept in a better way.
Find or Create the Mirror of a Binary tree in C++
Mirror of the binary tree is a tree in which all the left and right children of non-leaf nodes are interchanged.
Let’s see the example,
1 1 / \ / \ 2 3 ---> 3 2 / \ / \ / \ / \ 4 5 6 7 7 6 5 4
So, In the above example, we can understand the mirror of the binary tree in which left and right children of non-leaf node are interchanged.
We will use the recursive approach to find the mirror of the binary tree.
pseudocode for the recursive approach
Let’s see the pseudocode for the recursive approach to convert into mirror tree,
mirror(Node* root) if(root==NULL) then do return; mirror(root->left); mirror(root->right); Node* temp=root->left; root->left=root->right; root->right=temp;
So, we can easily understand the recursive approach in above pseudocode.
Code implementation in C++: Mirror of a binary tree
#include<iostream> #include<bits/stdc++.h> using namespace std; struct Node{ int data; Node* left; Node* right; }; Node* create(int x){ Node* temp=new Node; temp->data=x; temp->left=NULL; temp->right=NULL; return temp; } //function to find inorder traversal void inorder(Node* root){ if(root==NULL)return; inorder(root->left); cout<<root->data<<" "; inorder(root->right); } //funtion to convert into mirror tree void mirror(Node* root) { if(root==NULL)return; mirror(root->left); mirror(root->right); Node* temp=root->left; root->left=root->right; root->right=temp; } //main fuction int main(){ Node* root=create(1); root->left=create(2); root->left->right=create(5); root->left->left=create(4); root->right=create(3); root->right->left=create(6); root->right->right=create(7); mirror(root); cout<<"inorder traversal of the mirror of the binary tree is :"<<" "; inorder(root); return 0; }
Output
inorder traversal of the mirror of the binary tree is : 7 3 6 1 5 2 4
You may also learn,
Right view of the binary tree in C++
Leave a Reply