# How to find if two Binary trees are mirror images?

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