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:

Binary Trees
Binary Tree 1 & Binary Tree 2

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;
}

Here’s a working example:

https://ideone.com/QRf3zg

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;
}

Here’s a working example:

https://ideone.com/o6oi58

Leave a Reply

Your email address will not be published.