Home » Interview coding problems/challenges

Check Mirror in N-ary Tree

Check Mirror in N-ary Tree: Here, we are finding the solution of this problem, this problem and its application has been featured in interview round of many companies such as Amazon, DE-Shaw, Hike, MakeMyTrip etc.
Submitted by Divyansh Jaipuriyar, on June 24, 2020

Problem statement

Given two n-ary trees, the task is to check if they are mirrors of each other or not.

Note: you may assume that root of both the given tree as 1.

Input

The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two space-separated values N and M denoting the no. of nodes and edges respectively. Then in the next line, two lines are 2*M space-separated values u, v denoting an edge from u to v for both trees.

Output

For each test case in a new line print "YES" if both the trees are mirrors of each other else print "NO".

Examples

INPUT:	
T=1
N=3,M=3
1 2 1 3 2 4
1 3 1 2 2 4

OUTPUT: 
YES
    1                  1
   / \                / \
  2   3              3   2
 /                        \
 4                         4

Since they are mirror of each other.

INPUT:
T=1
N=4,M=4
1 2 1 3 2 4 2 5
1 3 1 2 2 4 2 5

OUTPUT: 
NO
    1                     1
   / \                   / \
  2   3                 3   2
 / \                       / \
4   5                     4   5

Here, 
node 4 and 5 are not as in mirror so the tree is not mirror.

Solution Approach

We will use stack and queue data structure since stack follow LIFO that is last in first out the way and queue follow FIFO first in first out pattern, is the trees are mirror then the top of the stack will be equal to the front of the queue and if they aren't equal it means that they are not the mirror of each other.

We will follow this approach, taking each node at a time and checking its connected component in stack and queue. For checking whether each subtree in itself is a mirror or not we will use a boolean variable flag, initially, the flag is true and each time we check if the top of stack and queue front are equal or not, if not then simply return NO as the answer and after checking all nodes return true if all are valid nodes.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        ll n, m;

        cout << "Enter number of nodes and edges: ";
        cin >> n >> m;

        // declare a vector of stacks of size (n+1)
        // since index start from 0.
        stack<int> v1[n + 1];
        // declare a vector of queue of size (n+1)
        // since index start from 0.
        queue<int> v2[n + 1];

        cout << "Enter tree 1: ";
        for (ll i = 0; i < m; i++) {
            ll x, y; //enter the elements of its.
            cin >> x >> y;
            v1[x].push(y);
        }

        cout << "Enter tree 2: ";
        for (ll i = 0; i < m; i++) {
            ll x, y;
            cin >> x >> y; //enter elements of tree 2.
            v2[x].push(y);
        }
        bool flag;
        // iterate through each node.
        for (int i = 1; i <= n; i++) {
            // store nodes of tree 1 connected components in stack
            stack<int>& s = v1[i];
            // store nodes of tree 1 connected components in queue
            queue<int>& q = v2[i];

            // declare a boolean variable to check mirror
            // property among the elements.
            flag = true;
            //compare the stack top to queue top.
            while (!s.empty() and !q.empty()) {
                // if not similar then break from the loop.
                if (s.top() != q.front()) {
                    flag = false;
                    break;
                }
                s.pop();
                q.pop();
            }
            // if not similar then break from the nodes loop
            // since no further comparison is needed.
            if (flag == false)
                break;
        }

        // check if mirror or not.
        cout << "Is Mirror: ";
        if (flag == true)
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter number of nodes and edges: 4 4 
Enter tree 1: 1 2 1 3 2 4 2 5
Enter tree 2: 1 2 1 3 2 5 2 4
Is Mirror: NO
Enter number of nodes and edges: 3 2
Enter tree 1: 1 2 1 3
Enter tree 2: 1 3 1 2
Is Mirror: YES
Enter number of nodes and edges: 3 3
Enter tree 1: 1 2 1 3 2 4
Enter tree 2: 1 3 1 2 2 4
Is Mirror: YES

• The time complexity for the above approach in worst case: O(n*n)
• Space complexity for the above approach in worst case : O(n)

---

Also tagged in: Amazon, DE-Shaw, Hike, MakeMyTrip

Problem source: https://practice.geeksforgeeks.org/problems/check-mirror-in-n-ary-tree/0