Mirror images mean right and left child of the two trees are interchanged. Thus, left child of first tree is right child of second tree. Consider the following image:
As you could see in the above image:
- Roots of Tree 1 and Tree 2 are same
- Left child of Tree 1 is Right Child of Tree 1
- Right Child of Tree 1 is Left Child of Tree 2
Approach 1
Traverse the Tree 1 and Tree 2 in Inorder fashion and store the node values of each Tree 1 & Tree 2 in two different arrays. You’ll find the two arrays to be reverse of each other if the trees are mirror images.
Code Implementation
//
// main.cpp
// Mirror Images
//
// Created by Himanshu on 04/09/21.
//
#include <iostream>
#include <queue>
using namespace std;
const int N = 5;
struct node {
int info = 0;
struct node *left, *right;
};
typedef struct node Node;
node* newNode(int data) {
node* Node = new node();
Node->info = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
void printArray (int arr[]) {
for (int i=0; i<N; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
}
bool checkMirrorImages (int A[], int B[]) {
//Check if two arrays are reverse of each other
for (int i=0, k=N-1; i<N && k>=0; i++, k--) {
if (A[i] != B[k]) {
return false;
}
}
return true;
}
void inorder (Node *root, int arr[], int &k) {
if (root == NULL) {
return;
}
// traverse left
inorder (root->left, arr, k);
// store root
arr[k++] = root->info;
// traverse right
inorder (root->right, arr, k);
}
int main() {
Node *root1 = newNode(1);
root1->left = newNode(20);
root1->right = newNode(21);
root1->right->left = newNode(30);
root1->right->right = newNode(31);
Node *root2 = newNode(1);
root2->left = newNode(21);
root2->right = newNode(20);
root2->left->left = newNode(31);
root2->left->right = newNode(30);
int A[N], B[N];
int k = 0;
inorder (root1, A, k);
k = 0;
inorder (root2, B, k);
cout<<"Array A:"<<endl;
printArray(A);
cout<<"Array B:"<<endl;
printArray(B);
if (checkMirrorImages(A, B)) {
cout<<"Trees are mirror Images"<<endl;
} else {
cout<<"Trees are not mirror Images"<<endl;
}
return 0;
}
Output
Array A: 20 1 30 21 31 Array B: 31 21 30 1 20 Trees are mirror Images
Here’s a working example: Binary trees (Mirror images)
Approach 2 (Using recursion)
Traverse the Tree 1 and Tree 2 together and check if:
- Current node of Tree 1 and Tree 2 are both NULL or,
- Current node of both trees are same and recursively check for left node of Tree 1 and right node of Tree 2.
Code Implementation
//
// main.cpp
// Mirror Images Recursive
//
// Created by Himanshu on 04/09/21.
//
#include <iostream>
#include <queue>
using namespace std;
const int N = 5;
struct node {
int info = 0;
struct node *left, *right;
};
typedef struct node Node;
node* newNode(int data) {
node* Node = new node();
Node->info = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
bool checkMirrorImages (Node *root1, Node *root2) {
//Check if two nodes are simultaneously NULL
if (root1 == NULL && root2 == NULL) {
return true;
} // return false if only one of them is NULL
else if (root1 == NULL || root2 == NULL) {
return false;
}
//Check root and its children (are interchanged)
if (root1->info == root2->info
&& checkMirrorImages(root1->left, root2->right)
&& checkMirrorImages(root1->right, root2->left)) {
return true;
} else {
return false;
}
}
int main() {
Node *root1 = newNode(1);
root1->left = newNode(20);
root1->right = newNode(21);
root1->right->left = newNode(30);
root1->right->right = newNode(31);
Node *root2 = newNode(1);
root2->left = newNode(21);
root2->right = newNode(20);
root2->left->left = newNode(30);
root2->left->right = newNode(31);
if (checkMirrorImages(root1, root2)) {
cout<<"Trees are mirror Images"<<endl;
} else {
cout<<"Trees are not mirror Images"<<endl;
}
return 0;
}
Output
Trees are not mirror Images
Here’s a working example: Binary trees (Mirror images) Recursion