{"id":10033,"date":"2022-09-28T10:08:08","date_gmt":"2022-09-28T10:08:08","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10033"},"modified":"2022-10-10T09:36:58","modified_gmt":"2022-10-10T09:36:58","slug":"check-mirror-in-n-ary-tree","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/check-mirror-in-n-ary-tree\/","title":{"rendered":"Check Mirror in N-ary Tree"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement:<\/h3>\n

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 \u201ctrue\u201d if they are mirror images of each other and \u201cfalse\u201d otherwise.<\/p>\n

Example:<\/h3>\n

Consider the two trees shown below.<\/p>\n

\"\"<\/p>\n

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.<\/p>\n

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.)<\/p>\n

Approach<\/h3>\n

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<\/a> containing the nodes connected to it.<\/p>\n

For instance, consider the tree T1 shown below.<\/p>\n

\"\"<\/p>\n

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.<\/p>\n

\"\"<\/p>\n

Next, we move to Node 20 by traversing the tree in preorder. <\/p>\n

So, 20 is added to the HashMap with the Stack of its children.<\/p>\n

![]()
\nNext, we move to Node 50. Here, we don’t have any children. Hence, the stack will be empty.<\/p>\n

\"\"
\nThe same will be the case with 60.<\/p>\n

\"\"<\/p>\n

So, this is what we have to do for the entire tree T1. <\/p>\n

Now, how will we check whether the trees T1 and T2 are mirror images or not? <\/p>\n

So, consider that we have filled the HashMap by traversing the tree T1 and we are now at tree T2.<\/p>\n

\"\"<\/p>\n

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.<\/p>\n

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. <\/p>\n

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.<\/p>\n

\"\"<\/p>\n

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. <\/p>\n

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.<\/p>\n

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.<\/p>\n

Now that we have understood this approach, let us write the code for the same.<\/p>\n

Code Implementation<\/h3>\n\t\t\t\t\t\t