Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Mirror Reflection

Last Updated on March 30, 2022 by Ria Pathak

DFS , Recursion

Medium

### Problem Statement :

Given two binary trees, we need to find whether one tree in the pair is the mirror image of another tree in the given pair.

See original problem statement here

### Solution Approach :

#### Introduction :

Given two trees, they are mirror images of each other if the left value of one tree is equal to the right node value of another tree or vice-versa.

#### Method 1 (Stack):

We can use two stacks (stack1 & stack2) to traverse both the trees. Perform normal inorder traversal with stack1 and reverse inorder traversal with stack2, while traversing both the trees check if the values are similar, if at any point there is a different value then it is not a mirror tree.

NOTE: In Reverse Inorder Traversal, we will traverse right node first followed by root node then left node (which is opposite as Inorder Traversal).

See C++ implementation.

#### Method 2 (Recursion) :

Given the root of two trees, `n1` & `n2`, the trees are mirror image of each other if they follow following properties :

• The root values of both trees should be equal.
• The values of the left & right node should be equal i.e `n1->left->value` must be equal to `n2->right->value`, for all subtrees.

If both the trees follows above properties, they are mirror tree, otherwise not.

### Solutions:

```#include <stdio.h>

#include<stdlib.h>

#include <stdbool.h>

#define ll long long

#define REP(i, n) for (i = 0; i < n; i++)

struct nodelist

{

ll value;

struct nodelist *left;

struct nodelist *right;

};

typedef struct nodelist node;

struct Queue

{

int front, rear, size;

unsigned capacity;

node* *array;

};

typedef struct Queue queue;

queue* createQueue(unsigned capacity)

{

queue* qu =(queue*)malloc(sizeof(queue));

qu->capacity = capacity;

qu->front = qu->size =0;

qu->rear = capacity-1;

qu->array = (node **)malloc(qu->capacity * sizeof(node));

return qu;

}

int isFull(queue*  queue1)

{

return (queue1->size == queue1->capacity);

}

int isEmpty(queue* queue1)

{

return (queue1->size==0);

}

void enqueue(queue* queue1, node* item)

{

if(isFull(queue1))

return ;

queue1->rear = (queue1->rear +1 )%queue1->capacity;

queue1->array[queue1->rear] = item;

queue1->size = queue1->size +1;

}

node dequeue(queue* queue1)

{

node* item = queue1->array[queue1->front];

queue1->front = (queue1->front +1)%queue1->capacity;

queue1->size = queue1->size -1;

return *item;

}

node* front(queue* queue1)

{

return queue1->array[queue1->front];

}

node* rear(queue * queue1)

{

return queue1->array[queue1->rear];

}

node *createNode(ll value)

{

node *t= (node *) malloc(sizeof(node));

t->value = value;

t->right = t->left = NULL;

return  t;

}

void deleteNode(node*t)

{

free(t);

}

node *replaceNegativeOne(node *root)

{

if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))

return NULL;

root->left = replaceNegativeOne(root->left);

root->right = replaceNegativeOne(root->right);

return root;

}

void deleteTree(node *node1)

{

if(node1==NULL)

return;

deleteTree(node1->left);

deleteTree(node1->right);

free(node1);

}

node *createTreeByLevelTree()

{

ll n,m;

queue* queue1 = createQueue(100000);

node *root, *t;

root = NULL;

while(scanf("%lld", &n))

{

if(isEmpty(queue1))

{

root= createNode(n);

enqueue(queue1,root);

continue;

}

scanf("%lld", &m);

t = front(queue1);

dequeue(queue1);

t->left =createNode(n);

t->right=createNode(m);

if(t->left->value !=-1)

enqueue(queue1,t->left);

if(t->right->value !=-1)

enqueue(queue1,t->right);

if(isEmpty(queue1))

break;

}

return root;

}

bool checkMirrorTree(node* a, node* b)

{

if(a==NULL && b==NULL)

return 1;

if(a->value != b->value)

return 0;

return checkMirrorTree(a->left,b->right) && checkMirrorTree(a->right,b->left);

}

int main() {

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

node *root2 = NULL;

root2 = createTreeByLevelTree();

root2 = replaceNegativeOne(root2);

if(checkMirrorTree(root,root2))

printf("true\n");

else

printf("false\n");

deleteTree(root);

return 0;

}
```
```#define REP(i, n) for (i = 0; i < n; i++)

#define pb(a) push_back(a)

#define vi vector<long>

#define ll long long

#include <bits/stdc++.h>

using namespace std;

struct node

{

ll value;

node *left;

node *right;

};

node *createNode(ll value)

{

node *t = new node();

t->value = value;

t->right = t->left = NULL;

return t;

}

void deleteNode(node *t)

{

delete t;

}

node *replaceNegativeOne(node *root)

{

if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))

return NULL;

root->left = replaceNegativeOne(root->left);

root->right = replaceNegativeOne(root->right);

return root;

}

node *createTreeByLevelTree()

{

ll n, m;

queue<node *> q;

node *root, *t;

root = NULL;

while (cin >> n)

{

if (q.empty())

{

root = createNode(n);

q.push(root);

continue;

}

cin >> m;

t = q.front();

q.pop();

t->left = createNode(n);

t->right = createNode(m);

if (t->left->value != -1)

{

q.push(t->left);

}

if (t->right->value != -1)

{

q.push(t->right);

}

if (q.empty())

{

break;

}

}

return root;

}

void deleteTree(node *node)

{

if (node == NULL)

return;

deleteTree(node->left);

deleteTree(node->right);

delete node;

}

bool checkMirrorTree(node* root1, node* root2)

{

stack<node*> st1, st2;

while (1)

{

while (root1 && root2)

{

if (root1->value != root2->value)

return 0;

st1.push(root1);

st2.push(root2);

root1 = root1->left;

root2 = root2->right;

}

if (!(root1 == NULL && root2 == NULL))

return 0;

if (!st1.empty() && !st2.empty())

{

root1 = st1.top();

root2 = st2.top();

st1.pop();

st2.pop();

root1 = root1->right;

root2 = root2->left;

}

else

break;

}

return 1;
}

int main()

{

node *root = NULL;

root = createTreeByLevelTree();

root = replaceNegativeOne(root);

node *root2 = NULL;

root2 = createTreeByLevelTree();

root2 = replaceNegativeOne(root2);

if(checkMirrorTree(root,root2))

cout<<"true"<<endl;

else

cout<<"false"<<endl;

deleteTree(root);

return 0;

}
```
```import java.util.LinkedList;

import java.util.*;

import java.util.Scanner;

import java.io.*;

class Node

{

long value;

Node left, right;

public Node(long item)

{

value = item;

left = right = null;

}

}

class BinaryTree {

Node root;

BinaryTree() {

root = null;

}

Node createNode(long value) {

Node t = new Node(value);

return t;

}

Node replaceNegativeOne(Node root) {

if (root == null || (root.value == -1 && root.left == null && root.right == null)) {

return null;

}

root.left = replaceNegativeOne(root.left);

root.right = replaceNegativeOne(root.right);

return root;

}

Node createTreeByLevelTree(Scanner sc) {

long n, m;

Node t;

root = null;

while (sc.hasNext()) {

n = sc.nextLong();

if (queue.isEmpty()) {

root = createNode(n);

continue;

}

m = sc.nextLong();

t.left = createNode(n);

t.right = createNode(m);

if (t.left.value != -1)

if (t.right.value != -1)

if (queue.isEmpty())

break;

}

return root;

}

void deleteTree(Node node) {

node = null;

}

boolean checkMirrorTree(Node node1, Node node2) {

if(node1 ==null  && node2==null)

return true;

if(node1.value != node2.value)

return false;

return checkMirrorTree(node1.left,node2.right) && checkMirrorTree(node1.right,node2.left);

}

}

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

BinaryTree bt = new BinaryTree();

bt.root = bt.createTreeByLevelTree(sc);

bt.root = bt.replaceNegativeOne(bt.root);

BinaryTree bt1 = new BinaryTree();

bt1.root = bt1.createTreeByLevelTree(sc);

bt1.root = bt1.replaceNegativeOne(bt1.root);

if(bt.checkMirrorTree(bt.root, bt1.root))

System.out.println("true");

else

System.out.println("false");

bt.deleteTree(bt.root);

}

}
```

[forminator_quiz id="1728"]

This article tried to discuss the concept of DFS , Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on DFS , Recursion you can check out MYCODE | Competitive Programming.