Last Updated on October 10, 2022 by Gokul Kannan
Problem Statement:
You are given 2 N-ary trees. You have to determine whether the 2 trees are mirror images of each other or not. You have to print “true” if they are mirror images of each other and “false” otherwise.
Example:
Consider the two trees shown below.
The two trees shown in the image are mirror images of each other. A mirror image means that each corresponding node in both the trees should have the same number of children and the order of children should be reversed. The order of children is reversed so that the node closest to the imaginary mirror in between them can remain closest in both the trees and the farther one remains farther.
As shown in the trees above, node 90 is closest to the mirror in the first tree and so is the case with the second tree as well. (The property of the mirror that the object in the mirror image is at an equal distance from the actual object from the mirror is followed.)
Approach
We will use a HashMap of Stacks to solve this problem. We will traverse the first tree completely and for each node in the first tree, we will add that node to the hashmap and corresponding to it, a Stack containing the nodes connected to it.
For instance, consider the tree T1 shown below.
So, currently, we are at node 10 or the root node of T1. We add the node to the HashMap and we also have a stack against the node value in the hashmap in which, we add all the children of Node 10 as shown below.
Next, we move to Node 20 by traversing the tree in preorder.
So, 20 is added to the HashMap with the Stack of its children.
![]()
Next, we move to Node 50. Here, we don’t have any children. Hence, the stack will be empty.
The same will be the case with 60.
So, this is what we have to do for the entire tree T1.
Now, how will we check whether the trees T1 and T2 are mirror images or not?
So, consider that we have filled the HashMap by traversing the tree T1 and we are now at tree T2.
Now, we are at Node 10 of the tree T2. We will go to Node 10 in the HashMap. If the HashMap does not contain node 10, the trees are not mirrored images of each other.
However, in this case, the HashMap contains node 10. So, we now traverse through the children of Node 10 in T2 and the stack corresponding to node 10 in the HashMap.
If the child of node 10 in T2 is present at the top of the Stack in the HashMap, we pop the value from the stack. If it is not present at the top of the stack, the trees are not mirrored images of each other.
For instance, in the image shown above, we see that when we were at 40, 40 was at the top of the stack. So, we popped it. Then, we came to node 30, and 30 was present at the top of the stack. So, we popped it as well. Similarly, we came to node 20 and it was present at the top of the stack. So, we popped it as well.
When we completed visiting the children of node 10, the stack also became empty. If the stack is not empty, the trees are not mirrored images of each other. If it is empty, perform the above operations for the next node.
Similarly, we have to do the same for the entire tree T2. In this case, we will find that T1 and T2 are mirror images of each other.
Now that we have understood this approach, let us write the code for the same.
Code Implementation
#include <bits/stdc++.h>
using namespace std;
int checkMirrorTree(int M, int N, int u1[ ],
int v1[ ] , int u2[], int v2[])
{
unordered_map<int , stack<int>>mp;
for (int i = 0 ; i < N ; i++ )
{
mp[u1[i]].push(v1[i]);
}
for (int i = 0 ; i < N ; i++)
{
if(mp[u2[i]].top() != v2[i])
return 0;
mp[u2[i]].pop();
}
return 1;
}
int main()
{
int M = 7, N = 6;
int u1[] = { 1, 1, 1, 10, 10, 10 };
int v1[] = { 10, 7, 3, 4, 5, 6 };
int u2[] = { 1, 1, 1, 10, 10, 10 };
int v2[] = { 3, 7, 10, 6, 5, 4 };
if(checkMirrorTree(M, N, u1, v1, u2, v2))
cout<<"Yes, the trees are mirror";
else
cout<<"No, they are not mirror";
return 0;
}
import java.util.*;
public class Main
{
static boolean checkMirrorTree(int M, int N, int[] u1, int[] v1, int[] u2, int[] v2)
{
HashMap<Integer, Stack<Integer>> mp = new HashMap<>();
for (int i = 0 ; i < N ; i++ )
{
if(!mp.containsKey(u1[i]))
{
mp.put(u1[i], new Stack<Integer>());
}
else{
mp.get(u1[i]).push(v1[i]);
}
}
for (int i = 0 ; i < N ; i++)
{
if(mp.containsKey(u2[i]) && mp.get(u2[i]).size() > 0)
{
if(mp.get(u2[i]).peek() != v2[i])
return false;
mp.get(u2[i]).pop();
}
}
return true;
}
public static void main(String[] args) {
int M = 7, N = 6;
int[] u1 = { 1, 1, 1, 10, 10, 10 };
int[] v1 = { 10, 7, 3, 4, 5, 6 };
int[] u2 = { 1, 1, 1, 10, 10, 10 };
int[] v2 = { 3, 7, 10, 6, 5, 4 };
if(checkMirrorTree(M, N, u1, v1, u2, v2))
System.out.print("Yes, they are mirror");
else
System.out.print("No, they are not mirror");
}
}
Time Complexity: The time complexity of this solution will be O(N) as we are traversing both trees once.
Space Complexity (Auxiliary Space): The space complexity is O(N) as we have used a HashMap that will contain all the N nodes of the tree T1.
So, the time complexity is O(N). However, using a HashMap is not a safe option. Usually, the HashMap can find a node in O(1) time. However, the worst case of HashMap for finding a key-value pair is O(N) because of excessive collisions.
So, in order to avoid this worst case, we can use another approach
Approach-2
We will create 2 lists. One lists will contain stacks and one will contain queues. We iterate over the first tree and fill the list of stacks as shown below.
Now, we iterate over the second tree and fill the list of queues as shown below.
Now, we will traverse both the lists corresponding to each node, we will pop an element from the stack and the queue. If they are equal, we continue else they are not mirror images of each other.
So, let us write the code for the above procedure too.
Code Implementation
import java.io.*;
import java.util.*;
class Main {
static int checkMirrorTree(int n, int e, int[] A, int[] B) {
List<Stack<Integer>> s = new ArrayList<>();
List<Queue<Integer>> q = new ArrayList<>();
for (int i = 0; i <= n; i++) {
s.add(new Stack<>());
Queue<Integer> queue = new LinkedList<>();
q.add(queue);
}
for (int i = 0; i < 2 * e; i += 2) {
s.get(A[i]).push(A[i + 1]);
q.get(B[i]).add(B[i + 1]);
}
for (int i = 1; i <= n; i++) {
while (!s.get(i).isEmpty() && !q.get(i).isEmpty()) {
int a = s.get(i).pop();
int b = q.get(i).poll();
if (a != b) {
return 0;
}
}
}
return 1;
}
public static void main (String[] args) {
int n = 3;
int e = 2;
int A[] = { 1, 2, 1, 3 };
int B[] = { 1, 3, 1, 2 };
if (checkMirrorTree(n, e, A, B) == 1) {
System.out.println("Yes, the trees are mirror");
} else {
System.out.println("No, the trees are not mirror");
}
}
}
Time Complexity: The time complexity of this solution will be O(N) as we are traversing both trees once.
Space Complexity (Auxiliary Space): The space complexity is O(N) as we have used 2 lists that will contain all the N nodes of the tree T1 and tree T2 respectively.
We tried to discuss Check Mirror in N-ary Tree. We hope this article gives you a better understanding of Check Mirror in N-ary Tree. PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.