Problem: Check Mirror in N-ary tree

*Difficulty: Medium

Given two n-ary tree’s the task is to check if they are mirror of each other or not.

Example

1                      1
/    \                 /   \
2      3             3     2

Output: 1

1                        1
/  \                    /  \
2    3                2     3

Output: 0

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 e denoting the no of nodes and edges respectively. Then in the next line two lines are 2*e space separated values u,v denoting an edge from u to v for the both trees .

Output:
For each test case in a new line print 1 if both the trees are mirrors of each other else print 0.

Constraints:
1<=T<=20
1<=n<=15
1<=e<=20

Example:
Input:

2
3 2
1 2 1 3
1 3 1 2
3 2
1 2 1 3
1 2 1 3
Output:
1
0

Approach: Since this is a N-arr tree, that means one node can have multiple child. So the easiest way is to consider it as a graph. Each graph has a list of adjacent nodes. The way to to check  if two threes (or graphs if you will) are mirror of each other or not is:

  1. They have the same number of nodes
  2. All node have the same number of adjacent nodes
  3. The child list of each node in the first tree when reversed will be exactly like the one in the node of second tree and vice versa.

Implementation: Python 3

def is_mirror(tree_1, tree_2):
    if len(tree_1) != len(tree_2):
        return False
    for node in tree_1:
        if len(tree_1[node]) != len(tree_2[node]):
            return False 
        if tree_1[node] != list(reversed(tree_2[node])):
            return False 
    return True 

def create_tree():
    tree = {}
    arr = list(map(int, input().strip().split()))
    for i in range(0,len(arr),2):
        if arr[i] in tree:
            tree[arr[i]].append(arr[i+1])
        else:
            tree[arr[i]] = [arr[i+1]]
    return tree

if __name__ == '__main__':
    t = int(input().strip())
    for _ in range(t):
        n, e = list(map(int, input().strip().split()))
        tree_1 = create_tree()
        tree_2 = create_tree()
        # print(tree_1)
        # print(tree_2)
        print(1 if is_mirror(tree_1, tree_2) else 0)
Advertisements