Check if all levels of two trees are anagrams or not Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/check-if-all-levels-of-two-trees-are-anagrams-or-not/1
(It is also the problem of the day for 19-November-2022)
Solution:
class Solution {
public static void fun(Node root,ArrayList<Integer>arr){
if(root==null){
return ;
}
else{
Queue<Node>queue=new LinkedList<Node>();
queue.add(root);
arr.add(root.data);
while(!queue.isEmpty()){
int a=queue.size();
for(int i=0;i<a;i++){
Node current=queue.remove();
arr.add(current.data);
if(current.right!=null){
queue.add(current.right);
}
if(current.left!=null){
queue.add(current.left);
}
}
}
}
}
public static boolean areAnagrams(Node node1, Node node2) {
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayList<Integer>ab=new ArrayList<Integer>();
fun(node1,aa);
fun(node2,ab);
if(aa.containsAll(ab)){
return true;
}
else{
return false;
}
}
}
Time Complexity:O(N)[All tree nodes are traversed][GFG Time:0.36]
Space Complexity:O(N)[Tree with N nodes]
Auxiliary Space:O(N)[ArrayLists are used]
Total Test Cases:353
Approach Used:
Here we need to find out whether all levels of trees are anagrams or not?
So for an anagram, if we observe carefully we can notice that the nodes' order may be different in both trees but when compared with each other they should be identical.
So for example for the first tree it
1-> 2 and 3
while for the second tree :
1->3 and 2
but nodes on the second level are the same and satisfy the condition of an anagram.
So keeping this in mind
we traversed the first tree and then the second tree and stored all the node's values in two ArrayList.
If both the ArrayList are the same then we return true else we return false.
-----------------------------------------------------------------------------------------------------------------------------
Second Approach:
Traversing the first tree in a different fashion and the second tree in a different fashion.
Traversing the first tree as root -> right -> left
and traversing the second tree as root->left->right
and then comparing both ArrayList.
If both ArrayList is the same then it means they are anagrams and hence return true, else they are not anagrams and return false.
Code:
class Solution {
public static void fun(Node root,ArrayList<Integer>arr){
if(root==null){
return ;
}
else{
Queue<Node>queue=new LinkedList<Node>();
queue.add(root);
arr.add(root.data);
while(!queue.isEmpty()){
int a=queue.size();
for(int i=0;i<a;i++){
Node current=queue.remove();
arr.add(current.data);
if(current.right!=null){
queue.add(current.right);
}
if(current.left!=null){
queue.add(current.left);
}
}
}
}
}
public static void fun2(Node root,ArrayList<Integer>arr){
if(root==null){
return ;
}
else{
Queue<Node>queue=new LinkedList<Node>();
queue.add(root);
arr.add(root.data);
while(!queue.isEmpty()){
int a=queue.size();
for(int i=0;i<a;i++){
Node current=queue.remove();
arr.add(current.data);
if(current.left!=null){
queue.add(current.left);
}
if(current.right!=null){
queue.add(current.right);
}
}
}
}
}
public static boolean areAnagrams(Node node1, Node node2) {
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayList<Integer>ab=new ArrayList<Integer>();
fun(node1,aa);
fun2(node2,ab);
if(aa.containsAll(ab)){
return true;
}
else{
return false;
}
}
}
Time Complexity:O(N)[All tree nodes are traversed][GFG Time:0.38]
Space Complexity:O(N)[Tree with N nodes]
Auxiliary Space:O(N)[ArrayLists are used]
Total Test Cases:353
-----------------------------------------------------------------------------------------------------------------------------
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😀"
Comments
Post a Comment