# Check if two trees are mirror tree of each other

Check if two trees are mirror tree of each other” is a basic problem based on tree data structure. Here, we are given two binary tree and our task is to write a program to check whether given two binary trees are mirror tree of each other.

Two trees are known as mirror tree of each other if they satisfy following conditions:

1. Both must be empty or non-empty tree.
2. Root Node data must be same.
3. Left subtree of first tree must be equal to right subtree of second tree.
4. Right subtree of first tree must be equal to left subtree of second tree.

#### C++ Program to check if two trees are mirror tree of each other is as follows:

```/* C++ Program to check if two trees are mirror tree of each other */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node *left;
struct Node *right;
Node(int ele)
{
data = ele;
left = NULL;
right = NULL;
}
} Node;

/* Function to check if two trees are mirror tree of each other */
bool checkMirror(Node *root1, Node *root2)
{
/* Base Case1: If both Trees are Empty */
if(root1 == NULL && root2 == NULL)
return true;

/* Base Case2: If one tree is empty and other not */
if(root1 == NULL || root2 == NULL)
return false;

/*
If Both are Non-Empty, Recursively compare data of left subtree of
first tree with right subtree of second tree and vice-versa
*/
return root1 -> data == root2 -> data &&
checkMirror(root1 -> left, root2 -> right) &&
checkMirror(root1 -> right,root2 -> left);
}

int main()
{
/* Creating a Binary trees and inserting some nodes in it */
Node *root1 = NULL;
Node *root2 = NULL;

/* Inserting some Nodes in first tree */
root1 = new Node(1);
root1 -> left = new Node(2);
root1 -> right = new Node(3);
root1 -> left -> left = new Node(4);
root1 -> left -> right = new Node(5);
root1 -> right -> left = new Node(6);
root1 -> right -> right = new Node (7);
root1 -> left -> right -> left = new Node(8);
root1 -> right -> left -> right = new Node(9);

/* Inserting some Nodes in second tree */
root2 = new Node(1);
root2 -> right = new Node(2);
root2 -> left = new Node(3);
root2 -> right -> right = new Node(4);
root2 -> right -> left = new Node(5);
root2 -> left -> right = new Node(6);
root2 -> left -> left = new Node (7);
root2 -> right -> left -> right = new Node(8);
root2 -> left -> right -> left = new Node(9);

/* Calling function to check if two trees are mirror tree of each other*/
if(checkMirror(root1,root2) == true)
{
cout<<"Both Trees are Mirror Tree of Each Other!!";
}
else
{
cout<<"Both Trees are not Mirror Tree of Each Other!!";
}

}
```

OUTPUT:

`Both Trees are Mirror Tree of Each Other!!`

Related Posts: