ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Check if 2 trees are mirror of each other

prodevelopertutorial March 30, 2020

In this tutorial we shall see how to check if 2 trees are mirror to each other.

 

Problem Statement:

 

You are given root node of 2 trees. You need to check if those 2 trees are mirror to each other.

 

For example:

 

Below 2 trees are mirror to each other.

 

Check if 2 nodes are mirror of each other

 

As you can see above, except root node, the left child will become right and vice versa. This is the meaning of mirror of binary tree.

 

From the above image we can arrive at below points that return true.

 

  1. If the current is root node, then continue.
  2. If the left child of the tree 1 is equal to the right child value return true.
  3. If the right child value is equal to the left child value, return true.
  4. If both are NULL, then return true.

 

We can also define below false statements:

 

  1. If right child exists in tree 1 and no child at tree 2 return false, same holds for vice versa.
  2. If the right child value is different than the left child value of tree 2, return false.

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(Node *node1, Node *node2) 
{
    if (node1 == NULL && node2 == NULL) 
    {
      return true;
    }

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

    return node1->data == node2->data 
        && check_if_mirror(node1->left, node2->right) 
        && check_if_mirror(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(root, root_1))
    {
        cout<<"Both are mirror"<<endl;
    } else {
        cout<<"Both are not mirror"<<endl;
    }

    return 0;  
}

Output:

Both are mirror

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io