Last Updated: 26 Feb, 2021

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

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 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:

We will use two arrays to store the level order traversal of both trees, “treeOne" and “treeTwo.”
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.
To start the traversal, we will push Root and Level =1 in the recursive function.
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.
We will similarly make an array for the second tree as well.
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.
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.
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.

Solve now

02 Approach

Approach:

This approach uses the concept of hashing.
Traverse every level of two trees simultaneously. For the first tree, store the element and frequency of the current level in a HashMap and for the second tree’s current level, if the current element is not present in HashMap then all the levels are not anagrams.
Otherwise, reduce the frequency of that element in the HashMap. If at the end of traversal, the HashMap is empty, then this level of both trees is an anagram and continues for the next levels, otherwise, all levels are not anagrams.

Algorithm:

Create two queues ‘treeOne’ and ‘treeTwo’, ‘treeOne’ is used to traverse tree 1 and ‘treeTwo’ is used to traverse tree 2.
Push the root of tree 1 to ‘treeOne’ and root of tree 2 to ‘treeTwo’.
While either ‘treeOne’ is not empty or ‘treeTwo’ is not empty perform the following steps:
- Create a HashMap ‘freq’ to store elements and frequency of current level elements. Initialize an integer ‘qSizeOne as the size of ‘treeOne’. Run a loop from 0 to less than ‘qSizeOne’. At every iteration pop out an element from the queue ‘treeOne’ and add it to the HashMap. Push the children of the current element into the queue.
- Initialize an integer ‘qSizeTwo’ as the size of ‘treeTwo’. Run a loop from 0 to less than ‘qSizeTwo’. At every iteration, pop out an element from the queue ‘treeTwo’ and if this element is present in HashMap reduce its frequency by 1, else return false immediately.
- If at the end of loop, HashMap contains an element, return false, else this level of the two trees are anagrams, continue for the next level.
If we reach here, all the levels of the two trees are anagrams, so return true.

Solve now

03 Approach

Algorithm:

We will use two queues to traverse the trees, i.e., treeOne and treeTwo.
Initially, we will push both the trees’ roots into their respective queues and run an infinite while loop until we have encountered that the trees are not anagram or have completed both the trees’ traversal.
At the start of each iteration of the while loop, the queues’ size will indicate the number of elements of the tree at a particular level, and this particular level will be the same for both the trees.
We maintain two arrays for both the trees, i.e., “currentTreeOne” and “currentTreeTwo,” to store the present elements at the current level.
Now, we will remove the queue element and push them into the current arrays, which we discussed in point 4.
While removing the node, we will push the children of that node into the queue.
At the end of each iteration, we will check whether the trees’ elements in the current array are the same or not. If they are not the same, then the function will return false.
If we have traversed both the trees, then it is clear that the trees are anagram, and the function will return true.

Solve now