Check for Mirror Trees

Moderate
0/80
5 upvotes
Asked in companies
AmazonMicrosoftHashedIn

Problem statement

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.

Example

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 
0 1
1 2
1 3
1 4
0 1
1 4
1 3
1 2
5
0 1
0 2
2 3
2 4
0 2
0 1
2 3
2 4
Sample Output 1:
YES
NO
Explanation of sample input 1:
For the first test case,

altimage

As from the image above, we can clearly see that these two N-ary trees are mirror images of each other. Hence, the answer is ‘YES’.



For the second test case,

altimage

The given two trees are not the mirror images because corresponding to the Node 4 of ‘TREE_A’, there exist Node3 of ‘TREE_B’.Hence, the answer is ‘NO’.
Sample Input 2:
2
5
0 1
0 2
1 3
1 4
0 2
0 1
1 4
1 3
5
0 1
0 2
1 4
2 3
0 1
0 2
1 3
3 4
Sample Output 2:
YES
NO
Hint

Check the order of the child nodes array.

Approaches (2)
Observation-based

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.
  • Given N-ary trees are mirror images.
  • Return ‘TRUE’.
Time Complexity

O(N), where N is the number of nodes in both the trees.

 

In this approach, we are just checking the child nodes list of each node. The total number of child nodes is equal to the number of edges, which is equal to the ‘N’-1. Hence, the overall time complexity is O(N).

Space Complexity

O(N), where N is the number of nodes in both the trees.

 

In this approach, we store both the trees in an adjacency list manner which takes O(N) corresponding to the number of edges(N-1). Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Check for Mirror Trees
Full screen
Console