Check if two binary trees are mirror | Set 3
Given two arrays, A[] and B[] consisting of M pairs, representing the edges of the two binary trees of N distinct nodes according to the level order traversal, the task is to check if trees are the mirror images of each other.
Examples:
Input: N = 6, M = 5, A[][2] = {{1, 5}, {1, 4}, {5, 7}, {5, 8}, {4, 9}}, B[][2] = {{1, 4}, {1, 5}, {4, 9}, {5, 8}, {5, 7}}
Output: Yes
Explanation:Input: N = 5, M = 4, A[][2] = {{10, 20}, {10, 30}, {20, 40}, {20, 50}}, B[][2] = {{10, 30}, {10, 20}, {20, 40}, {20, 50}}
Output: No
Explanation:
Approach: The given problem can be solved using Map and Set data structures. Follow the steps below to solve the problem:
- Initialize two, maps of vectors say T1 and T2 to store the adjacency list of trees A and B respectively.
- Initialize a set say St to store all the unique nodes’ values.
- Traverse the array A[] using the variable i, and performing the following steps:
- Push the value A[i][1] into the vector T1[A[i][0]] and then append the A[i][0] and A[i][1] to the set St.
- As the edges are given according to the level order traversal, therefore in tree A for all nodes, the left child was inserted first and then the right child was inserted.
- Traverse the array B[] in reverse order using the variable i and performing the following steps:
- Push the value B[i][1] into the vector T2[B[i][0]] and then append the B[i][0] and B[i][1] to the set St.
- As array B[] is traversed in reverse, therefore in the tree B for all nodes, the right child was inserted first and then the left child was inserted.
- Now iterate over the of set St and check if the vectors of children of the current node in tree A are not equal to the vectors of children of the current node in tree B, then print “No” as the answer and then return.
- Finally, if none of the above cases satisfy, then print “Yes” as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether two binary // trees are mirror image of each other // or not string checkMirrorTree( int N, int M, int A[][2], int B[][2]) { // Stores the adjacency list // of tree A map< int , vector< int > > T1; // Stores the adjacency list // of tree B map< int , vector< int > > T2; // Stores all distinct nodes set< int > st; // Traverse the array A[] for ( int i = 0; i < M; i++) { // Push A[i][1] in the // vector T1[A[i][0]] T1[A[i][0]].push_back(A[i][1]); // Insert A[i][0] in the // set st st.insert(A[i][0]); // Insert A[i][1] in the // set st st.insert(A[i][1]); } // Traverse the array B[] in // reverse for ( int i = M - 1; i >= 0; i--) { // Push B[i][1] in the // vector T2[B[i][0]] T2[B[i][0]].push_back(B[i][1]); // Insert B[i][0] in the // set st st.insert(B[i][0]); // Insert B[i][0] in the // set st st.insert(B[i][1]); } // Iterate over the set st for ( auto node : st) { // If vector T1[node] is // not equals to T2[node] if (T1[node] != T2[node]) return "No" ; } // Return "Yes" as // the answer return "Yes" ; } // Driver Code int main() { // Given Input int N = 6; int M = 5; int A[][2] = { { 1, 5 }, { 1, 4 }, { 5, 7 }, { 5, 8 }, { 4, 9 } }; int B[][2] = { { 1, 4 }, { 1, 5 }, { 4, 9 }, { 5, 8 }, { 5, 7 } }; // Function Call cout << checkMirrorTree(N, M, A, B); return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { // Function to check whether two binary // trees are mirror image of each other // or not static String checkMirrorTree( int N, int M, int [][] A, int [][] B) { // Stores the adjacency list // of tree A HashMap<Integer, Vector<Integer>> T1 = new HashMap<Integer, Vector<Integer>>(); // Stores the adjacency list // of tree B HashMap<Integer, Vector<Integer>> T2 = new HashMap<Integer, Vector<Integer>>(); // Stores all distinct nodes Set<Integer> st = new HashSet<Integer>(); // Traverse the array A[] for ( int i = 0 ; i < M; i++) { // Push A[i][1] in the // vector T1[A[i][0]] if (T1.containsKey(A[i][ 0 ])) { T1.get(A[i][ 0 ]).add(A[i][ 1 ]); } else { T1.put(A[i][ 0 ], new Vector<Integer>()); T1.get(A[i][ 0 ]).add(A[i][ 1 ]); } // Insert A[i][0] in the // set st st.add(A[i][ 0 ]); // Insert A[i][1] in the // set st st.add(A[i][ 1 ]); } // Traverse the array B[] in // reverse for ( int i = M - 1 ; i >= 0 ; i--) { // Push B[i][1] in the // vector T2[B[i][0]] if (T2.containsKey(B[i][ 0 ])) { T2.get(B[i][ 0 ]).add(B[i][ 1 ]); } else { T2.put(B[i][ 0 ], new Vector<Integer>()); T2.get(B[i][ 0 ]).add(B[i][ 1 ]); } // Insert B[i][0] in the // set st st.add(B[i][ 0 ]); // Insert B[i][0] in the // set st st.add(B[i][ 1 ]); } // Iterate over the set st for ( int node : st) { // If vector T1[node] is // not equals to T2[node] if (!(T1.get(node) == T2.get(node))) return "Yes" ; } // Return "No" as // the answer return "No" ; } public static void main(String[] args) { // Given Input int N = 6 ; int M = 5 ; int [][] A = { { 1 , 5 }, { 1 , 4 }, { 5 , 7 }, { 5 , 8 }, { 4 , 9 } }; int [][] B = { { 1 , 4 }, { 1 , 5 }, { 4 , 9 }, { 5 , 8 }, { 5 , 7 } }; // Function Call System.out.print(checkMirrorTree(N, M, A, B)); } } // This code is contributed by rameshtravel07. |
Python3
# Py program for the above approach # Function to check whether two binary # trees are mirror image of each other # or not def checkMirrorTree(N, M, A, B): # Stores the adjacency list # of tree A T1 = [[] for i in range ( 100 )] # Stores the adjacency list # of tree B T2 = [[] for i in range ( 100 )] # Stores all distinct nodes st = {} # Traverse the array A[] for i in range (M): # Push A[i][1] in the # vector T1[A[i][0]] T1[A[i][ 0 ]].append(A[i][ 1 ]) # Insert A[i][0] in the # set st st[A[i][ 0 ]] = 1 # Insert A[i][1] in the # set st st[A[i][ 1 ]] = 1 # Traverse the array B[] in # reverse for i in range (M - 1 , - 1 , - 1 ): # Push B[i][1] in the # vector T2[B[i][0]] T2[B[i][ 0 ]].append(B[i][ 1 ]) # Insert B[i][0] in the # set st st[B[i][ 0 ]] = 1 # Insert B[i][0] in the # set st st[B[i][ 1 ]] = 1 # Iterate over the set st for node in st: # If vector T1[node] is # not equals to T2[node] if (T1[node] ! = T2[node]): return "No" # Return "Yes" as # the answer return "Yes" # Driver Code if __name__ = = '__main__' : # Given Input N = 6 M = 5 A = [ [ 1 , 5 ], [ 1 , 4 ], [ 5 , 7 ], [ 5 , 8 ], [ 4 , 9 ]] B = [ [ 1 , 4 ],[ 1 , 5 ],[ 4 , 9 ],[ 5 , 8 ],[ 5 , 7 ]] # Function Call print (checkMirrorTree(N, M, A, B)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to check whether two binary // trees are mirror image of each other // or not static string checkMirrorTree( int N, int M, int [,] A, int [,] B) { // Stores the adjacency list // of tree A Dictionary< int , List< int >> T1 = new Dictionary< int , List< int >>(); // Stores the adjacency list // of tree B Dictionary< int , List< int >> T2 = new Dictionary< int , List< int >>(); // Stores all distinct nodes HashSet< int > st = new HashSet< int >(); // Traverse the array A[] for ( int i = 0; i < M; i++) { // Push A[i][1] in the // vector T1[A[i][0]] if (T1.ContainsKey(A[i,0])) { T1[A[i,0]].Add(A[i,1]); } else { T1[A[i,0]] = new List< int >(); T1[A[i,0]].Add(A[i,1]); } // Insert A[i][0] in the // set st st.Add(A[i,0]); // Insert A[i][1] in the // set st st.Add(A[i,1]); } // Traverse the array B[] in // reverse for ( int i = M - 1; i >= 0; i--) { // Push B[i][1] in the // vector T2[B[i][0]] if (T2.ContainsKey(B[i,0])) { T2[B[i,0]].Add(B[i,1]); } else { T2[B[i,0]] = new List< int >(); T2[B[i,0]].Add(B[i,1]); } // Insert B[i][0] in the // set st st.Add(B[i,0]); // Insert B[i][0] in the // set st st.Add(B[i,1]); } // Iterate over the set st foreach ( int node in st) { // If vector T1[node] is // not equals to T2[node] if (!T1[node].Equals(T2[node])) return "Yes" ; } // Return "No" as // the answer return "No" ; } static void Main() { // Given Input int N = 6; int M = 5; int [,] A = { { 1, 5 }, { 1, 4 }, { 5, 7 }, { 5, 8 }, { 4, 9 } }; int [,] B = { { 1, 4 }, { 1, 5 }, { 4, 9 }, { 5, 8 }, { 5, 7 } }; // Function Call Console.Write(checkMirrorTree(N, M, A, B)); } } // This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for the above approach // Function to check whether two binary // trees are mirror image of each other // or not function checkMirrorTree(N, M, A, B) { // Stores the adjacency list // of tree A let T1 = []; // Stores the adjacency list // of tree B let T2 = []; for (let i = 0; i < 100; i++) { T1.push([]); T2.push([]); } // Stores all distinct nodes let st = new Map(); // Traverse the array A[] for (let i = 0; i < M; i++) { // Push A[i][1] in the // vector T1[A[i][0]] T1[A[i][0]].push(A[i][1]); // Insert A[i][0] in the // set st st[A[i][0]] = 1; // Insert A[i][1] in the // set st st[A[i][1]] = 1; } // Traverse the array B[] in // reverse for (let i = M - 1; i < -1; i=-1) { // Push B[i][1] in the // vector T2[B[i][0]] T2[B[i][0]].push(B[i][1]); // Insert B[i][0] in the // set st st[B[i][0]] = 1; // Insert B[i][0] in the // set st st[B[i][1]] = 1; } // Iterate over the set st st.forEach((values,node)=>{ // If vector T1[node] is // not equals to T2[node] if (T1[node] != T2[node]) { return "No" ; } }) // Return "Yes" as // the answer return "Yes" ; } // Given Input let N = 6; let M = 5; let A = [ [1, 5], [1, 4], [5, 7], [5, 8], [4, 9]]; let B = [ [ 1, 4 ],[ 1, 5 ],[ 4, 9 ],[ 5, 8 ],[ 5, 7 ]]; // Function Call document.write(checkMirrorTree(N, M, A, B)); // This code is contributed by divyeshrabadiya07. </script> |
Output
Yes
Time Complexity: O((N+M)*log(N))
Auxiliary Space: O(N+M)