Check if Two Trees are Mirror Structure to each other

Question:

Given a 2 binary trees root nodes, check if the structure is mirror to each other.

Example:

Consider the image given below and its mirror.

Image 8

If you can see in the above image, both the trees structure are mirror to each other.

We don’t consider the node elements, we just consider the structure.

So to solve this problem, we need to check if right node is present in tree 1, then left node should be present in tree 2 and vice versa.

By doing so we can check if both of the trees have mirror structure.

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


bool check_if_mirror_structure(Node *node1, Node *node2) 
{
    if (node1 == NULL && node2 == NULL) 
    {
      return true;
    }

    if (node1 == NULL || node2 == NULL) 
    {
      return false;
    }

    return check_if_mirror_structure(node1->left, node2->right) && check_if_mirror_structure(node1->right, node2->left);
  }




int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);



    Node* root_1 = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          25      10
         /  \    /  \
        /    \  /    \
       30    18 15     7

    */

    root_1 = new Node(16);
    root_1->left = new Node(25);
    root_1->right = new Node(10);
    root_1->left->left = new Node(30);
    root_1->left->right = new Node(18);
    root_1->right->left = new Node(15);
    root_1->right->right = new Node(7);

    if(check_if_mirror_structure(root, root_1))
    {
        cout<<"Both are mirror structure"<<endl;
    } else {
        cout<<"Both are not mirror structure"<<endl;
    }

    return 0;  
}  

Output:

Both are mirror structure