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

belongs to collection: Interview C++ coding problems/challenges | tree

mahmoud2506

Save to bookmark

2022-04-30

215

Check Mirror in N-ary Tree

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.

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-04-30

need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)