C++ program to Check if two trees are Mirror

In this tutorial, we are going to learn how to check if two trees are mirrors or not in C++. Here we will learn about mirror trees, how to determine if two trees are mirror of each others. After that, we will see the C++ program for the same.

Mirror Trees

Two trees are said to be mirrors of each other when their structures are mirror images of each other. The left subtree of the root node of the first tree is the same as the right subtree of the root node of the second tree and vice-e-versa. See the example, both the trees are the mirror of each other.

Mirror trees

Algorithm to check if two trees are mirror

We can check that the given two trees are the mirror of each other by traversing both the trees simultaneously and compare each node.

Algorithm:-
1. Pass the root pointer of both the trees to check function.
2. Check that the trees are not empty. If both the trees are empty return 1.
3. Else, compare the data of both nodes.
4. Recursively, call the left subtree of tree 1 and right subtree of tree 2.
5. And, recursively, call the right subtree of tree 1 and left subtree of tree 2.
6. If point  3,4,5 are true, return 1.
7. Else, return 0.

C++ program to check if two trees are mirror or not.

So, here is the C++ implementation of the above algorithm:-

#include<bits/stdc++.h>
using namespace std;
//Structure of a node of the tree  
  
struct TreeNode
{  
    int val;  
    TreeNode *left;  
    TreeNode *right;  
};           

/*===========================================
FUNCTION TO CREATE NEW NODE FOR TREE
============================================*/
TreeNode* makeTreeNode(int data)
{                                               
    TreeNode *newTreeNode = new TreeNode();      
    newTreeNode->val = data;                     
    return newTreeNode;  
}
/*===========================================
FUNCTION TO CHECK IF TWO TREES ARE MIRROR.
============================================*/
int check_mirror(TreeNode *root1,TreeNode *root2)
{
  //If trees are empty return true                                               
    if(root1==NULL && root2==NULL)
    	return 1;
    //If trees are not empty
    if(root1!=NULL && root2!=NULL)
    {
    	int a,b,c;
    	//compare data if equal then a=1
    	a=(root1->val==root2->val);
    	//Recursively, check left subtree of tree1 
    	//and right subtree of tree 2
    	b=check_mirror(root1->left,root2->right);
    	//Recursively, check right subtree of tree1
    	//and left subtree of tree 2
    	c=check_mirror(root1->right,root2->left);
    	// If a,b and c are true then return true
    	if(a && b && c)
    		return 1;
    }
    return 0;
} 
/*======================================
   MAIN FUNCTION
=======================================*/
int main()  
{  
    TreeNode *root1, *root2;          
    //Make tree1 by calling 
    //function makeTreeNode()  
    root1 = makeTreeNode(1);  
    root1->left = makeTreeNode(2);  
    root1->left->left = makeTreeNode(3);  
    root1->left->right = makeTreeNode(4);   
    root1->right = makeTreeNode(5);  
    root1->right->right = makeTreeNode(7);  
    //Representation of input tree1
    //                  1
    //                /   \
    //               /     \
    //              2       5
    //            /   \      \
    //           3     4      7


    //Make tree2 by calling 
    //function makeTreeNode()  
    root2 = makeTreeNode(1);  
    root2->left = makeTreeNode(5);  
    root2->left->left = makeTreeNode(7);  
    root2->right = makeTreeNode(2);  
    root2->right->left = makeTreeNode(4);  
    root2->right->right = makeTreeNode(3); 
    //Representation of input tree2
    //                  1
    //                /   \
    //               /     \
    //              5       2
    //             /       /  \
    //            7       4    3
      
    //Calling check_mirror function that checks 
    //that the two trees are mirror or not  
    int ans=check_mirror(root1,root2);  
    if(ans)
    cout<<"YES, trees are mirror."<<endl;  
  else
    cout<<"NO, trees are not mirror."<<endl;  
   
    return 0;  
}

Output:-

YES, trees are mirror.

Time Complexity:- O(n)

Thanks for reading this tutorial. I hope it helps you !!

Leave a Reply

Your email address will not be published. Required fields are marked *