Check mirror in n-ary tree

Last Updated : 16 Jan, 2023

Given two n-ary trees, the task is to check if they are the mirror of each other or not. Print “Yes” if they are the mirror of each other else “No”.

Examples:

Input : Node = 3, Edges = 2
Edge 1 of first N-ary: 1 2
Edge 2 of first N-ary: 1 3
Edge 1 of second N-ary: 1 3
Edge 2 of second N-ary: 1 2
Output : Yes

Input : Node = 3, Edges = 2
Edge 1 of first N-ary: 1 2 
Edge 2 of first N-ary: 1 3
Edge 1 of second N-ary: 1 2
Edge 2 of second N-ary: 1 3
Output : No

Recommended PracticeCheck Mirror in N-ary treeTry It!

Approach 1: (Using Hashing)

The idea is to use an unordered map of stacks to check if given N-ary tree are mirror of each other or not.
Let the first n-ary tree be t1 and the second n-ary tree is t2. For each node in t1, push its connected node in their corresponding stack in the map. Now, for each node in t2, their connected node match with the top of the stack, then pop elements from the stack.

Otherwise, if the node does not match with the top of the stack then it means two trees are not mirror of each other.

Now, for each corresponding node do the following:

  1. Iterate over map of stack
      Push all connected nodes of each node of first tree in map of  stack.

  2. Again iterate over map for each node of second tree
      For example :     

      Let us take one node X of second tree 
      
      For this node X , check in map which stack is used

      a = Top of that stack for node X present in second tree;
      b = Connected node of X in second tree
      if (a != b)
           return false;
      pop node X from stack.

Implementation:

C++

// C++ program to check if two n-ary trees are
// mirror.
#include <bits/stdc++.h>
using namespace std;
 
// Function to check given two trees are mirror
// of each other or not
int checkMirrorTree(int M, int N, int u1[ ], 
                    int v1[ ] , int u2[], int v2[]) 
    {
        // Map to store nodes of the tree
        unordered_map<int , stack<int>>mp;
   
        // Traverse first tree nodes
        for (int i = 0 ; i < N ; i++ )
        {
           mp[u1[i]].push(v1[i]);
        }
         
        // Traverse second tree nodes
        for (int i = 0 ; i < N ; i++)
        {
            if(mp[u2[i]].top() != v2[i]) 
                  return 0;
            mp[u2[i]].pop();
        }
   
        return 1;
    }
 
// Driver code
int main()
{
    int M = 7, N = 6;
     
    //Tree 1
    int u1[] = { 1, 1, 1, 10, 10, 10 };
    int v1[] = { 10, 7, 3, 4, 5, 6 };
   
    //Tree 2
    int u2[] = { 1, 1, 1, 10, 10, 10 };
    int v2[] = { 3, 7, 10, 6, 5, 4 };
 
    if(checkMirrorTree(M, N, u1, v1, u2, v2))
       cout<<"Yes";
    else
       cout<<"No";
   
    return 0;
}

Java

// Java program to check if two n-ary trees are mirror.
import java.util.*;
public class Main
{
    // Function to check given two trees are mirror
    // of each other or not
    static boolean checkMirrorTree(int M, int N, int[] u1, int[] v1, int[] u2, int[] v2)
    {
        
        // Map to store nodes of the tree
        HashMap<Integer, Stack<Integer>> mp = new HashMap<>();
     
        // Traverse first tree nodes
        for (int i = 0 ; i < N ; i++ )
        {
           if(!mp.containsKey(u1[i]))
           {
               mp.put(u1[i], new Stack<Integer>());
           }
           else{
               mp.get(u1[i]).push(v1[i]);
           }
        }
           
        // Traverse second tree nodes
        for (int i = 0 ; i < N ; i++)
        {
            if(mp.containsKey(u2[i]) && mp.get(u2[i]).size() > 0)
            {
                if(mp.get(u2[i]).peek() != v2[i])
                  return false;
                mp.get(u2[i]).pop();
            }
        }
     
        return true;
    }
     
  // Driver code
    public static void main(String[] args) {
        int M = 7, N = 6;
       
        // Tree 1
        int[] u1 = { 1, 1, 1, 10, 10, 10 };
        int[] v1 = { 10, 7, 3, 4, 5, 6 };
         
        // Tree 2
        int[] u2 = { 1, 1, 1, 10, 10, 10 };
        int[] v2 = { 3, 7, 10, 6, 5, 4 };
       
        if(checkMirrorTree(M, N, u1, v1, u2, v2))
           System.out.print("Yes");
        else
           System.out.print("No");
    }
}
 
// This code is contributed by divyeshrabadiya07.

Python3

# Python3 program to check if two n-ary trees are mirror.
 
# Function to check given two trees are mirror
# of each other or not
def checkMirrorTree(M, N, u1, v1, u2, v2):
    # Map to store nodes of the tree
    mp = {}
 
    # Traverse first tree nodes
    for i in range(N):
        if u1[i] in mp:
            mp[u1[i]].append(v1[i])
        else:
            mp[u1[i]] = []
      
    # Traverse second tree nodes
    for i in range(N):
        if u2[i] in mp and len(mp[u2[i]]) > 0:
            if(mp[u2[i]][-1] != v2[i]):
                return 0
            mp[u2[i]].pop()
    return 1
 
M, N = 7, 6
      
#Tree 1
u1 = [ 1, 1, 1, 10, 10, 10 ]
v1 = [ 10, 7, 3, 4, 5, 6 ]
 
#Tree 2
u2 = [ 1, 1, 1, 10, 10, 10 ]
v2 = [ 3, 7, 10, 6, 5, 4 ]
 
if(checkMirrorTree(M, N, u1, v1, u2, v2)):
   print("Yes")
else:
   print("No")
     
    # This code is contributed by rameshtravel07.

C#

// C# program to check if two n-ary trees are mirror.
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to check given two trees are mirror
    // of each other or not
    static bool checkMirrorTree(int M, int N, int[] u1, int[] v1, int[] u2, int[] v2)
    {
       
        // Map to store nodes of the tree
        Dictionary<int, Stack<int>> mp = new Dictionary<int, Stack<int>>(); 
    
        // Traverse first tree nodes
        for (int i = 0 ; i < N ; i++ )
        {
           if(!mp.ContainsKey(u1[i]))
           {
               mp[u1[i]] = new Stack<int>();
           }
           else{
               mp[u1[i]].Push(v1[i]);
           }
        }
          
        // Traverse second tree nodes
        for (int i = 0 ; i < N ; i++)
        {
            if(mp.ContainsKey(u2[i]) && mp[u2[i]].Count > 0)
            {
                if(mp[u2[i]].Peek() != v2[i])
                  return false;
                mp[u2[i]].Pop();
            }
        }
    
        return true;
    }
     
  // Driver code
  static void Main() 
  {
    int M = 7, N = 6;
      
    // Tree 1
    int[] u1 = { 1, 1, 1, 10, 10, 10 };
    int[] v1 = { 10, 7, 3, 4, 5, 6 };
    
    // Tree 2
    int[] u2 = { 1, 1, 1, 10, 10, 10 };
    int[] v2 = { 3, 7, 10, 6, 5, 4 };
  
    if(checkMirrorTree(M, N, u1, v1, u2, v2))
       Console.Write("Yes");
    else
       Console.Write("No");
  }
}
 
// This code is contributed by mukesh07.

Javascript

// JavaScript code for the above approach
 
// Function to check given two trees are mirror
// of each other or not
function checkMirrorTree(M, N, u1, v1, u2, v2) {
    // Map to store nodes of the tree
    let mp = {}
 
    // Traverse first tree nodes
    for (let i = 0; i < N; i++) {
        if (u1[i] in mp) {
            mp[u1[i]].push(v1[i]);
        } else {
            mp[u1[i]] = [v1[i]];
        }
    }
 
    // Traverse second tree nodes
    for (let i = 0; i < N; i++) {
        if (u2[i] in mp && mp[u2[i]].length > 0) {
            if (mp[u2[i]][mp[u2[i]].length - 1] != v2[i]) {
                return 0;
            }
            mp[u2[i]].pop();
        }
    }
    return 1;
}
 
let M = 7,
    N = 6;
 
//Tree 1
let u1 = [1, 1, 1, 10, 10, 10];
let v1 = [10, 7, 3, 4, 5, 6];
 
//Tree 2
let u2 = [1, 1, 1, 10, 10, 10];
let v2 = [3, 7, 10, 6, 5, 4];
 
if (checkMirrorTree(M, N, u1, v1, u2, v2)) {
    console.log("Yes");
} else {
    console.log("No");
}
 
// This code is contributed by Potta Lokesh

Output

Yes

Time Complexity: O(N).
Auxiliary Space: O(N).

Approach 2: (Using LinkedList):

The main approach is to use one list of stack and one list of queue to store to value of nodes given in the form of two arrays.

Initialize both the lists with empty stack and empty queues respectively.

Now, iterate over the lists
Push all connected nodes of each node of first tree in list of stack and second tree list of queue.

Now iterate over the array and pop item from both stack and queue and check if they are same, if not same then return 0.

Implementation:

C++

// C++ program to check two n-ary trees are mirror.
#include <bits/stdc++.h>
using namespace std;
 
// Function to check given two trees are mirror
// of each other or not
int checkMirrorTree(int n, int e, int A[], int B[])
{
    //Lists to store nodes of the tree
    vector<stack<int>> s;
    vector<queue<int>> q;
 
    // initializing both list with empty stack and queue
    for (int i = 0; i <= n; i++)
    {
        s.push_back(stack<int>());
        queue<int> queue;
        q.push_back(queue);
    }
 
    // add all nodes of tree 1 to list of stack and tree 2 to list of queue
    for (int i = 0; i < 2 * e; i += 2)
    {
        s[A[i]].push(A[i + 1]);
        q[B[i]].push(B[i + 1]);
    }
 
    // now take out the stack and queues
    // for each of the nodes and compare them
    // one by one
    for (int i = 1; i <= n; i++)
    {
        while (!s[i].empty() && !q[i].empty())
        {
            int a = s[i].top();
            s[i].pop();
            int b = q[i].front();
            q[i].pop();
 
            if (a != b)
            {
                return 0;
            }
        }
    }
 
    return 1;
}
 
int main()
{
    int n = 3;
    int e = 2;
    int A[] = {1, 2, 1, 3};
    int B[] = {1, 3, 1, 2};
 
    if (checkMirrorTree(n, e, A, B) == 1)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
 
    return 0;
}
// This code is added by Srj_27

Java

// Java program to check two n-ary trees are mirror.
 
import java.io.*;
import java.util.*;
 
class GFG {
   
      // Function to check given two trees are mirror
    // of each other or not
      static int checkMirrorTree(int n, int e, int[] A, int[] B) {
 
          //Lists to store nodes of the tree
        List<Stack<Integer>> s = new ArrayList<>();
        List<Queue<Integer>> q = new ArrayList<>();
 
        // initializing both list with empty stack and queue
        for (int i = 0; i <= n; i++) {
            s.add(new Stack<>());
            Queue<Integer> queue = new LinkedList<>();
            q.add(queue);
        }
 
           // add all nodes of tree 1 to list of stack and tree 2 to list of queue
        for (int i = 0; i < 2 * e; i += 2) {
            s.get(A[i]).push(A[i + 1]);
            q.get(B[i]).add(B[i + 1]);
        }
 
          // now take out the stack and queues
        // for each of the nodes and compare them
        // one by one
        for (int i = 1; i <= n; i++) {
            while (!s.get(i).isEmpty() && !q.get(i).isEmpty()) {
                int a = s.get(i).pop();
                int b = q.get(i).poll();
 
                if (a != b) {
                    return 0;
                }
            }
        }
 
        return 1;
    }
   
    public static void main (String[] args) {
        int n = 3;
        int e = 2;
        int A[] = { 1, 2, 1, 3 };
        int B[] = { 1, 3, 1, 2 };
 
        if (checkMirrorTree(n, e, A, B) == 1) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
 
    }
}

Python3

# Python3 program to check two n-ary trees are mirror.
 
# Function to check given two trees are mirror
# of each other or not
def checkMirrorTree(n, e, A, B):
    # Lists to store nodes of the tree
    s = []
    q = []
 
    # initializing both list with empty stack and queue
    for i in range(n + 1):
        s.append([])
        queue = []
        q.append(queue)
 
   # add all nodes of tree 1 to
   # list of stack and tree 2 to list of queue
    for i in range(0, 2 * e, 2):
        s[A[i]].append(A[i + 1])
        q[B[i]].append(B[i + 1])
 
    # now take out the stack and queues
    # for each of the nodes and compare them
    # one by one
    for i in range(1, n + 1):
        while (len(s[i]) > 0 and len(q[i]) > 0):
            a = s[i][len(s[i]) - 1]
            s[i].pop()
            b = q[i][0]
            q[i].pop(0)
 
            if (a != b):
                return 0
    return 1
 
  # Driver code
n = 3
e = 2
A = [ 1, 2, 1, 3 ]
B = [ 1, 3, 1, 2 ]
 
if (checkMirrorTree(n, e, A, B) == 1):
    print("Yes")
else:
    print("No")
     
    # This code is contributed by decode2207.

C#

// C# program to check two n-ary trees are mirror.
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
     
    // Function to check given two trees are mirror
    // of each other or not
    static int checkMirrorTree(int n, int e, int[] A, int[] B) 
    {
        //Lists to store nodes of the tree
        List<Stack> s = new List<Stack>();
        List<Queue> q = new List<Queue>();
  
        // initializing both list with empty stack and queue
        for (int i = 0; i <= n; i++) {
            s.Add(new Stack());
            Queue queue = new Queue();
            q.Add(queue);
        }
  
           // add all nodes of tree 1 to list of stack and tree 2 to list of queue
        for (int i = 0; i < 2 * e; i += 2) {
            s[A[i]].Push(A[i + 1]);
            q[B[i]].Enqueue(B[i + 1]);
        }
  
          // now take out the stack and queues
        // for each of the nodes and compare them
        // one by one
        for (int i = 1; i <= n; i++) {
            while (s[i].Count > 0 && q[i].Count > 0) {
                int a = (int)s[i].Pop();
                int b = (int)q[i].Dequeue();
  
                if (a != b) {
                    return 0;
                }
            }
        }
  
        return 1;
    }
     
  static void Main() {
    int n = 3;
    int e = 2;
    int[] A = { 1, 2, 1, 3 };
    int[] B = { 1, 3, 1, 2 };
 
    if (checkMirrorTree(n, e, A, B) == 1) {
        Console.Write("Yes");
    } else {
        Console.Write("No");
    }
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
    // Javascript program to check two n-ary trees are mirror.
     
    // Function to check given two trees are mirror
    // of each other or not
      function checkMirrorTree(n, e, A, B) {
  
          //Lists to store nodes of the tree
        let s = [];
        let q = [];
  
        // initializing both list with empty stack and queue
        for (let i = 0; i <= n; i++) {
            s.push([]);
            let queue = [];
            q.push(queue);
        }
  
           // add all nodes of tree 1 to 
           // list of stack and tree 2 to list of queue
        for (let i = 0; i < 2 * e; i += 2) {
            s[A[i]].push(A[i + 1]);
            q[B[i]].push(B[i + 1]);
        }
  
          // now take out the stack and queues
        // for each of the nodes and compare them
        // one by one
        for (let i = 1; i <= n; i++) {
            while (s[i].length > 0 && q[i].length > 0) {
                let a = s[i][s[i].length - 1];
                s[i].pop();
                let b = q[i][0];
                q[i].shift();
  
                if (a != b) {
                    return 0;
                }
            }
        }
  
        return 1;
    }
     
    let n = 3;
    let e = 2;
    let A = [ 1, 2, 1, 3 ];
    let B = [ 1, 3, 1, 2 ];
 
    if (checkMirrorTree(n, e, A, B) == 1) {
      document.write("Yes");
    } else {
      document.write("No");
    }
    
   // This code is contributed by suresh07.
</script>

Output

Yes

Time complexity: O(N) where N is no of nodes in given n-ary tree
Auxiliary space: O(N)

Reference: https://www.geeksforgeeks.org/problems/check-mirror-in-n-ary-tree/0

GeeksforGeeks

Improve

Previous Article

Number of nodes greater than a given value in n-ary tree

Replace every node with depth in N-ary Generic Tree

Similar Reads

Check if a number is prime in Flipped Upside Down, Mirror Flipped and Mirror Flipped Upside Down

Given an integer N, the task is to check if N is a prime number in Flipped Down, Mirror Flipped and Mirror Flipped Down forms of the given number.Examples: Input: N = 120121 Output: YesExplanation: Flipped forms of the number:Flipped Upside Down - 151051Mirror Flipped - 121021Mirror Upside Down - 150151Since 1510151 and 121021 are both prime number

Mirror of n-ary Tree

Given a Tree where every node contains variable number of children, convert the tree to its mirror. Below diagram shows an example. We strongly recommend you to minimize your browser and try this yourself first. Node of tree is represented as a key and a variable sized array of children pointers. The idea is similar to mirror of Binary Tree. For ev

Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)

Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Recommended PracticeMirror TreeTry It!The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees. Follow

Check if the given n-ary tree is a binary tree

Given an n-ary tree, the task is to check whether the given tree is binary or not. Examples: Input: A / \ B C / \ \ D E F Output: Yes Input: A / | \ B C D \ F Output: No Approach: Every node in a binary tree can have at most 2 children. So, for every node of the given tree, count the number of children and if for any node the count exceeds 2 then p

Create a mirror tree from the given binary tree

Given a binary tree, the task is to create a new binary tree which is a mirror image of the given binary tree. Examples: Input: 5 / \ 3 6 / \ 2 4 Output: Inorder of original tree: 2 3 4 5 6 Inorder of mirror tree: 6 5 4 3 2 Mirror tree will be: 5 / \ 6 3 / \ 4 2 Input: 2 / \ 1 8 / \ 12 9 Output: Inorder of original tree: 12 1 2 8 9 Inorder of mirro

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver

Build a segment tree for N-ary rooted tree

Prerequisite: Segment tree and depth first search.In this article, an approach to convert an N-ary rooted tree( a tree with more than 2 children) into a segment tree is discussed which is used to perform a range update queries. Why do we need a segment tree when we already have an n-ary rooted tree? Many times, a situation occurs where the same ope

Remove all leaf nodes from a Generic Tree or N-ary Tree

Given a Generic tree, the task is to delete the leaf nodes from the tree. Examples: Input: 5 / / \ \ 1 2 3 8 / / \ \ 15 4 5 6 Output: 5 : 1 2 3 1 : 2 : 3 : Explanation: Deleted leafs are: 8, 15, 4, 5, 6 Input: 8 / | \ 9 7 2 / | \ | / / | \ \ 4 5 6 10 11 1 2 2 3 Output: 8: 9 7 2 9: 7: 2: Approach: Follow the steps given below to solve the problem Co

Count of nodes in given N-ary tree such that their subtree is a Binary Tree

Given an N-ary tree root, the task is to find the count of nodes such that their subtree is a binary tree. Example: Input: Tree in the image below Output: 11Explanation: The nodes such that there subtree is a binary tree are {2, 8, 10, 6, 7, 3, 1, 9, 5, 11, 12}. Input: Tree in the image below Output: 9 Approach: The given problem can be solved by u

Tree of Space - Locking and Unlocking N-Ary Tree

Given a world map in the form of Generic M-ary Tree consisting of N nodes and an array queries[], the task is to implement the functions Lock, Unlock and Upgrade for the given tree. For each query in queries[], the functions return true when the operation is performed successfully, otherwise it returns false. The functions are defined as: X: Name o

Article Tags :

Practice Tags :