Check Mirror Tree

Given two n-ary trees.?Check if they are mirror images of each other or not. You are also given e denoting the number of edges in both trees, and two arrays, A[] and B[]. Each array has?2*e space separated values u,v denoting an edge from u to v for the both trees.

?? View Full Code??

Approach :

• For each node in Tree 1 (using array A), store its children in an unordered_map where the key is the node, and the value is an array that will store its children in the order they appear in A.
• Do the same process for Tree 2 using array B.
• To make Tree 2 a mirror of Tree 1, reverse the map of children in map2 for each node.
• For each node in the range [1, n], check if map1[node] is equal to map2[node] after reversing map2.
• If any node’s children don’t match, return 0 (not mirror images). Otherwise, return 1.

int checkMirrorTree(int n, int e, int A[], int B[]) {
        
        unordered_map<int, vector<int>>m1, m2;
        
        for(int i=0 ; i<2*e ; i+=2){
            
            m1[A[i]].push_back(A[i+1]);
            m2[B[i]].push_back(B[i+1]);
        }
        
        for(int i=1 ; i<n+1 ; i++){
            reverse(m1[i].begin(), m1[i].end());
            
            if(m1[i] != m2[i]){
                return 0;
            }
        }
        return 1;   
    }        

Time Complexity : O(e)

Space Complexity : O(e)

?? View GitHub Repo ??