Last Updated on March 30, 2022 by Ria Pathak
Concepts Used
DFS , Recursion
Difficulty Level
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->valuemust be equal ton2->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;
Queue<Node> queue = new LinkedList<>();
Node t;
root = null;
while (sc.hasNext()) {
n = sc.nextLong();
if (queue.isEmpty()) {
root = createNode(n);
((LinkedList<Node>) queue).add(root);
continue;
}
m = sc.nextLong();
t = ((LinkedList<Node>) queue).peekFirst();
((LinkedList<Node>) queue).pop();
t.left = createNode(n);
t.right = createNode(m);
if (t.left.value != -1)
((LinkedList<Node>) queue).add(t.left);
if (t.right.value != -1)
((LinkedList<Node>) queue).add(t.right);
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) {
// write your code here
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.