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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions