Last Updated: 21 Nov, 2021
Check for Mirror Trees
Moderate
Asked in companies
While learning DSA, Ninja found two N-ary trees and wants to check whether they are mirror images of each other or not. But, he can’t find a suitable method to check the same. Can you help Ninja to solve this problem?
You are given two N-ary trees, ‘TREEA’ and ‘TREEB’ having ‘N’ vertices labeled from 0 to ‘N’-1, and both the trees are rooted at node 0. Your task is to find whether the trees are mirror images of each other or not. Edges of the tree are in order from left to right.
For Example:
For the given example below, the trees are mirror images of each other.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, the ‘N’ denoting the number of vertices in both the trees.
Next, ‘N’-1 lines have two integers i,j, denoting an edge between vertex i and vertex j in ‘TREE_A’.
Next, ‘N’-1 lines have two integers i,j, denoting an edge between vertex i and vertex j in ‘TREE_B’.
Output Format:
For each test case, print ‘YES’ if both the trees are mirror images of each other.
Print the output of each test case in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 1000.
0 <= Node Label <=N-1.
Time limit: 1 sec
Approaches
We can simply observe the pattern that if the trees are mirror images of each other, then the i’th node of TREE_A and i’th node of TREE_B should have an equal number of child nodes and the same set of child nodes but in reverse order as they should form the mirror images.
In this approach, we will simply check the ‘TREE_A[i]’ and ‘TREE_B[i]’ for all labels from 0 to ‘N’-1 and check whether they consist of the same set of child nodes in reverse order or not. If we find any discrepancy, we will return ‘FALSE’.Else the answer will be ‘TRUE’.
Algorithm:
- Declare an array of ‘N+1’ dynamic arrays ‘TREE_A’ to store the tree in an adjacency list manner.
- Declare an array of ‘N+1’ dynamic arrays ‘TREE_B’ to store the tree in an adjacency list manner.
- For ‘EDGE’ in ‘EDGES_A’:
- Insert EDGE[0] into ‘TREE_A[ EDGE[1] ]’.
- For ‘EDGE’ in ‘EDGES_B’:
- Insert EDGE[0] into ‘TREE_B[ EDGE[1] ]’.
- The trees are prepared.
- For i in the range from 0 to N-1, do the following:
- If the length of ‘TREE_A[i]’ is not equal to the length of ‘TREE_B[i]’:
- Both have an unequal number of child nodes.
- Return ‘FALSE’.
- Set j as 0.
- Set k as the length of ‘TREE_A[i]’ -1.
- While k is greater than -1, do the following:
- If TREE_A[i][j] is not equal to TREE_B[i][k]:
- Different values found.
- Return ‘FALSE’.
- Set j as j+1.
- Set k as k-1.
- If TREE_A[i][j] is not equal to TREE_B[i][k]:
- If the length of ‘TREE_A[i]’ is not equal to the length of ‘TREE_B[i]’:
- Given N-ary trees are mirror images.
- Return ‘TRUE’.
In this approach, we will first traverse the first tree in a preorder manner and store the nodes in a stack, and for the second tree, we will traverse the tree in a postorder manner and store the nodes in a queue. We are using stack and queue because we want to check the reverse order, and we know that Stack follows FIFO(First In First Out) and Queue follows FILO(First In Last Out). After the traversals, we will pop values one by one from the stack and queue and compare them. If we find any discrepancy, we will return ‘FALSE’.Otherwise, the trees are mirror images, we will return ‘TRUE’.
Algorithm:
- Declare fillStack(‘CUR’,’TREE_A’,’S’):
- Push ‘CUR’ into stack ‘S’.
- Recursive calls for all child nodes of the ‘CUR’ node.
- For i in ‘TREE_A[CUR]’, do the following:
- Call fillStack(‘i’,’TREE_A’,S).
- Declare fillQueue(‘CUR’,’TREE_B’,’Q’):
- Recursive calls for all child nodes of the ‘CUR’ node.
- For i in ‘TREE_A[CUR]’, do the following:
- Call fillQueue(‘i’,’TREE_A’,S).
- Push ‘CUR’ into queue ‘Q’.
- Declare an array of ‘N+1’ dynamic arrays ‘TREE_A’ to store the tree in an adjacency list manner.
- Declare an array of ‘N+1’ dynamic arrays ‘TREE_B’ to store the tree in an adjacency list manner.
- For ‘EDGE’ in ‘EDGES_A’:
- Insert EDGE[0] into ‘TREE_A[ EDGE[1] ]’.
- For ‘EDGE’ in ‘EDGES_B’:
- Insert EDGE[0] into ‘TREE_B[ EDGE[1] ]’.
- The trees are prepared.
- Declare a stack ‘S’ and a queue ‘Q’.
- Call fillStack(0,’TREE_A’,’S’).
- Call fillQueue(0,’TREE_B’,’Q’).
- Now, compare the values of popped out.
- While Q is not empty, do the following:
- Set ‘A’ as top of stack ‘S’.
- Pop an element from ‘S’.
- Set ‘B’ as the front element of queue ‘Q’.
- Pop an element from ‘Q’.
- If ‘A’ is not equal to ‘B’:
- Return ‘FALSE’.
- Given N-ary trees are mirror images.
- Return ‘TRUE’.