Check If All Levels Of Two Trees Are Anagrams Of Each Other Not

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in company
Clearwater Analytics

Problem statement

You’re given two binary trees. Your task is to check if all the trees’ levels are anagrams of each other. If they’re anagram of each other, print ‘Yes’ else print ‘No.’

Note :

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains two integers denoting N and M, denoting the number of nodes in Tree one and Tree two.

The second line of each test contains the first tree elements in the level order form separated by a single space. If any node does not have a left or right child, take -1 in its place. 

The third line of each test contains the elements of the second tree in the level order form separated by a single space. If any node does not have a left or right child, take -1 in its place. 

Refer to the example below.

Alt text

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

alt text

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output Format :

For every test case, print “Yes” of the given binary trees is an anagram of each other, else print “No.”

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <=  N <= 100

Where N is the number of nodes.

Time limit: 1 sec

Sample Input 1:

1
3 3
1 2 3 -1 -1 -1 -1 
1 3 2 -1 -1 -1 -1

Sample Output 1:

Yes
Explanation of Sample Input 1:
The first level of both trees is an anagram of each other since it only has 1. The second level of the first tree contains elements 2, 3, which is also an anagram, to the second tree’s second level, including elements 3,2.

Alt text

Sample Input 2 :

1
5 5
1 3 2 -1 -1 5 4 -1 -1 -1 -1 
1 2 3 4 5 -1 -1 -1 -1 -1 -1

Sample Output 2 :

Yes

Explanation of Sample Input 2 :

The first level of both trees contains 1. Hence they are an anagram of each other. The second level of the first tree has 3,2, is an anagram to the second level of the second tree, which contains 2,3, and the third level of the first tree contains 5,4, which is also an anagram to the third level of the second tree, which includes 4,5.

Alt text

Hint

Nodes at each level should be equal.

Approaches (3)
Recursion based approach

We’ll recursively perform level order traversal for both trees and store this result of traversals in two different arrays. Then we’ll sort both of these arrays and iterate on the levels. For each level, if they are the same, return ‘true’ else return ‘false.’

 

Algorithm:

 

  1. We will use two arrays to store the level order traversal of both trees, “treeOne" and “treeTwo.”
  2. Then, we will perform level order traversal with the help of a recursive function in which the arguments will be the node and its level.
  3. To start the traversal, we will push Root and Level =1 in the recursive function.
  4. In the recursive function, if the node value is NULL, the function will return; otherwise, we will push back the current node in the treeOne[level] array and make a recursive call child with their level values = level+1.
  5. We will similarly make an array for the second tree as well.
  6. Now, when we have traversed both the trees, then we need to check whether, at each level, there are similar nodes in both the trees or not.
  7. To check what we discussed in point 6, we will go from level 1 to level N and, firstly, sort both the arrays at each level for easier comparison.
  8. Then, we will compare the sorted arrays, and if they are not equal at any level, we will return false otherwise, we will return true.
Time Complexity

O(N + M), Where N is the number of nodes in tree 1 and M is the number of nodes in tree 2

 

We are traversing every level of the tree and considering each node only once. Hence, our final time complexity will be O(N + M). 

Space Complexity

O(N + M), Where N is the number of nodes in tree 1 and M is the number of nodes in tree 2


 

As there can be utmost N entries in the first sorted array and M entries in second sorted array which will take O(N + M) space and the recursion stack will take O(N) space for tree1 and O(M) space for tree2. Hence, the space complexity will be O(N + M) + O(N + M) = O(N + M).

Code Solution
(100% EXP penalty)
Check If All Levels Of Two Trees Are Anagrams Of Each Other Not
Full screen
Console