Posted on by Kalkicode
Code Queue

# Check if all levels of two trees are anagrams or not

The problem involves checking if all levels of two binary trees are anagrams of each other or not. Anagrams in the context of binary trees mean that the nodes at each level of both trees have the same values, regardless of their positions.

## Problem Statement

Given two binary trees, the task is to determine whether all the levels of the two trees are anagrams of each other.

## Example Scenario

Consider the following three binary trees:

1. First Tree:
``````     8
/   \
7     4
/     /  \
3     9    2
/ \
5   6``````
2. Second Tree:
``````     8
/   \
4     7
/  \    \
2    9    3
/ \
6   5``````
3. Third Tree:
``````     8
/   \
4     7
/  \    \
2    6    3
\
9
\
5``````

For the first two trees, all levels are anagrams of each other, while for the third tree, not all levels are anagrams.

## Idea to Solve the Problem

To solve this problem, we can perform a level-order traversal of both trees simultaneously and compare the nodes at each level to check if they are anagrams or not.

## Pseudocode

``````void is_anagrams(struct TreeNode *tree1, struct TreeNode *tree2)
{
// Create queues for both trees
// Enqueue the root nodes of both trees

while (both queues are not empty)
{
// Dequeue nodes from both queues
// Check if nodes at the current level are anagrams
// Enqueue the left and right children of the nodes in the queues
}

// Check if both queues are empty
// If not, trees are not anagrams at all levels
}``````

## Algorithm Explanation

1. Implement the `is_anagrams` function that takes the root nodes of both trees as input.
2. Create queues for both trees using the `make_queue` function.
3. Enqueue the root nodes of both trees into their respective queues.
4. Start a loop that continues as long as both queues are not empty.
5. Inside the loop, dequeue nodes from both queues.
6. Check if the nodes at the current level are anagrams using some suitable technique (e.g., compare sorted arrays of node values).
7. If the nodes are anagrams, enqueue the left and right children of the nodes into their respective queues.
8. After the loop ends, check if both queues are empty. If not, it means trees are not anagrams at all levels.

## Code Solution

``````/*
C Program
Check if all levels of two trees are anagrams or not
*/
#include <stdio.h>
#include <stdlib.h>

//Queue node
struct QueueNode
{
int level;
struct TreeNode *element;
struct QueueNode *next;
};
// Define queue
struct MyQueue
{

struct QueueNode*front;
struct QueueNode*tail;

};

// Binary Tree node
struct TreeNode
{
int data;
struct TreeNode *left, *right;
};

struct BinaryTree
{
struct TreeNode*root;
};

struct MyQueue* make_queue()
{

// Create dynamic node of MyQueue
struct MyQueue *node = (struct MyQueue *) malloc(sizeof(struct MyQueue));

if(node==NULL)
{
printf("\nMemory Overflow, when creating a new Queue\n");
}
else
{
node->front = NULL;
node->tail  = NULL;
}
return node;
}

struct BinaryTree* make_tree()
{

// Create dynamic node of BinaryTree
struct BinaryTree *node = (struct BinaryTree *) malloc(sizeof(struct BinaryTree));

if(node==NULL)
{
printf("\nMemory Overflow, when creating a new BinaryTree\n");
}
else
{
node->root = NULL;
}
return node;
}
int is_empty(struct MyQueue*queue)
{
if(queue == NULL || queue->front==NULL)
{
return 1;
}
else
{
return 0;
}
}

//Create a queue node and returns this node
void enqueue(struct MyQueue*queue , struct TreeNode *tree_node)
{
//Make a new Queue node
struct QueueNode *new_node = (struct QueueNode *) malloc(sizeof(struct QueueNode));

if (new_node != NULL)
{
//Set node values
new_node->element = tree_node;
new_node->next    = NULL;

if(queue->front==NULL)
{
queue->front = new_node;

queue->tail  = queue->front;
}
else
{
queue->tail->next = new_node;

queue->tail = new_node;
}
}
else
{
printf("\nMemory Overflow, when creating a new Queue Node\n");
}

}

//Remove a queue elements
void dequeue(struct MyQueue*queue)
{
if ( is_empty(queue)==0)
{
struct QueueNode *remove = queue->front;

if(queue->front==queue->tail)
{
queue->tail = NULL;
}

queue->front= queue->front->next;

remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}

// Return front element of queue
struct TreeNode* peek(struct MyQueue*queue)
{
if(is_empty(queue)==1)
{
return NULL;
}
else
{
return queue->front->element;
}
}
void inorder(struct TreeNode*node)
{
if(node!=NULL)
{

inorder(node->left);
printf("  %d",node->data);
inorder(node->right);
}
}
// Determine two trees are anagram or not
void is_anagrams(struct TreeNode*tree1,struct TreeNode*tree2)
{

//result indicators
int status = 1;

// Create queue variables
struct MyQueue *queue1 = make_queue();

struct MyQueue *queue2 = make_queue();

// Add first node of queue
enqueue(queue1,tree1);
enqueue(queue2,tree2);

// Define tree nodes
struct TreeNode *node1 = NULL;
struct TreeNode *node2 = NULL;

//print tree elements
printf("\n First Tree \n");
inorder(tree1);
printf("\n Second Tree \n");
inorder(tree2);
//
while(is_empty(queue1)==0 || is_empty(queue2)==0)
{

if(status==1)
{
// Get the front element of both queue
node1 = peek(queue1);
node2 = peek(queue2);

if(
(  node1  == NULL && node2 != NULL)
|| (node1 != NULL && node2 == NULL)
|| (node1 != NULL && node2 != NULL  && node1->data != node2->data))
{
//When both queue front node are not same (That is based on values or null nodes )
status = 0;
}
else
{
if(node1->left != NULL)
{

enqueue(queue1,node1->left);
}
if(node1->right != NULL)
{
enqueue(queue1,node1->right);
}

if(node2->right!=NULL)
{
enqueue(queue2,node2->right);
}
if(node2->left!=NULL)
{
enqueue(queue2,node2->left);
}

dequeue(queue1);
dequeue(queue2);

}
}
else
{
if(is_empty(queue1)==0)
{
dequeue(queue1);
}
if(is_empty(queue2)==0)
{
dequeue(queue2);
}
status = 0;
}

}

if(status==0)
{
printf("\n Anagram not exist \n");
}
else
{
printf("\n Anagram exist \n");
}

}

//This is creating a binary tree node and return new node
struct TreeNode *get_tree_node(int data)
{
// Create dynamic node
struct TreeNode *new_node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("\nMemory Overflow, when creating a new Tree Node\n");
}
//return new node
return new_node;
}

int main()
{
struct BinaryTree*tree1= make_tree();
struct BinaryTree*tree2= make_tree();
struct BinaryTree*tree3= make_tree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
tree1->root = get_tree_node(8);
tree1->root->left = get_tree_node(7);
tree1->root->left->left = get_tree_node(3);
tree1->root->right = get_tree_node(4);
tree1->root->right->left = get_tree_node(9);
tree1->root->right->right = get_tree_node(2);
tree1->root->right->left->left = get_tree_node(5);
tree1->root->right->left->right = get_tree_node(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/

tree2->root = get_tree_node(8);
tree2->root->right = get_tree_node(7);
tree2->root->right->right = get_tree_node(3);
tree2->root->left = get_tree_node(4);
tree2->root->left->right = get_tree_node(9);
tree2->root->left->left = get_tree_node(2);
tree2->root->left->right->right = get_tree_node(5);
tree2->root->left->right->left = get_tree_node(6);

/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------
Third Constructing binary tree
*/

tree3->root = get_tree_node(8);
tree3->root->right = get_tree_node(7);
tree3->root->right->right = get_tree_node(3);
tree3->root->left = get_tree_node(4);
tree3->root->left->right = get_tree_node(6);
tree3->root->left->left = get_tree_node(2);
tree3->root->left->right->right = get_tree_node(9);
tree3->root->left->right->right->right = get_tree_node(5);

// Test case
is_anagrams(tree1->root,tree2->root);
is_anagrams(tree2->root,tree3->root);

return 0;
}``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist``````
``````/*
Java Program
Check if all levels of two trees are anagrams or not
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}

// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public QueueNode(TreeNode element)
{
this.element = element;
this.next = null;

}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element)
{
QueueNode new_node = new QueueNode(element);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}

public boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
public TreeNode peek()
{
if(is_empty()==false)
{
return this.front.element;
}
else
{
return null;
}
}
}
//Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
//Set root of tree
this.root = null;
}
public void inorder(TreeNode node)
{
if(node!=null)
{

inorder(node.left);
System.out.print("  "+node.data);
inorder(node.right);
}
}
// Determine two trees are anagram or not
public void is_anagrams(TreeNode root2)
{
//result indicators
boolean status = true;
// Create queue variables
MyQueue queue1 = new MyQueue();
MyQueue queue2 = new MyQueue();
// Add first node of queue
queue1.enqueue(this.root);
queue2.enqueue(root2);
// Define tree nodes
TreeNode node1 = null;
TreeNode node2 = null;
//print tree elements
System.out.print("\n First Tree \n");
inorder(this.root);
System.out.print("\n Second Tree \n");
inorder(root2);
//
while (queue1.is_empty() == false || queue2.is_empty() == false)
{
if (status == true)
{
// Get the front element of both queue
node1 = queue1.peek();
node2 = queue2.peek();
if ((node1 == null && node2 != null) || (node1 != null && node2 == null) || (node1 != null && node2 != null && node1.data != node2.data))
{
//When both queue front node are not same (That is based on values or null nodes )
status = false;
}
else
{
if (node1.left != null)
{
queue1.enqueue(node1.left);
}
if (node1.right != null)
{
queue1.enqueue(node1.right);
}
if (node2.right != null)
{
queue2.enqueue(node2.right);
}
if (node2.left != null)
{
queue2.enqueue(node2.left);
}
queue1.dequeue();
queue2.dequeue();
}
}
else
{
if (queue1.is_empty() == false)
{
queue1.dequeue();
}
if (queue2.is_empty() == false)
{
queue2.dequeue();
}
status = false;
}
}
if (status == false)
{
System.out.print("\n Anagram not exist \n");
}
else
{
System.out.print("\n Anagram exist \n");
}
}

public static void main(String[] args)
{

BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
BinaryTree tree3 = new BinaryTree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
tree1.root = new TreeNode(8);
tree1.root.left = new TreeNode(7);
tree1.root.left.left = new TreeNode(3);
tree1.root.right = new TreeNode(4);
tree1.root.right.left = new TreeNode(9);
tree1.root.right.right = new TreeNode(2);
tree1.root.right.left.left = new TreeNode(5);
tree1.root.right.left.right = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/
tree2.root = new TreeNode(8);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(3);
tree2.root.left = new TreeNode(4);
tree2.root.left.right = new TreeNode(9);
tree2.root.left.left = new TreeNode(2);
tree2.root.left.right.right = new TreeNode(5);
tree2.root.left.right.left = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------
Third Constructing binary tree
*/
tree3.root = new TreeNode(8);
tree3.root.right = new TreeNode(7);
tree3.root.right.right = new TreeNode(3);
tree3.root.left = new TreeNode(4);
tree3.root.left.right = new TreeNode(6);
tree3.root.left.left = new TreeNode(2);
tree3.root.left.right.right = new TreeNode(9);
tree3.root.left.right.right.right = new TreeNode(5);
//inorder(tree1->root);
// Test case
tree1.is_anagrams(tree2.root);
tree2.is_anagrams(tree3.root);
}
}``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Check if all levels of two trees are anagrams or not
*/

//  Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
//  Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
//  Queue Node
class QueueNode
{
public:
TreeNode *element;
QueueNode *next;
QueueNode(TreeNode *element)
{
this->element = element;
this->next = NULL;
}
};
// Define custom queue class
class MyQueue
{
public: QueueNode *front;
QueueNode *tail;
MyQueue()
{
this->front = NULL;
this->tail = NULL;
}
// Add a new node at last of queue
void enqueue(TreeNode *element)
{
QueueNode *new_node = new QueueNode(element);
if (this->front == NULL)
{
// When first node of queue
this->front = new_node;
}
else
{
// Add node at last position
this->tail->next = new_node;
}
this->tail = new_node;
}
// Delete first node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
}
}
bool is_empty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
TreeNode *peek()
{
if (this->is_empty() == false)
{
return this->front->element;
}
else
{
return NULL;
}
}
};
// Define Binary Tree
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
// Set root of tree
this->root = NULL;
}
void inorder(TreeNode *node)
{
if (node != NULL)
{
this->inorder(node->left);
cout << "  " << node->data;
this->inorder(node->right);
}
}
//  Determine two trees are anagram or not
void is_anagrams(TreeNode *root2)
{
// result indicators
bool status = true;
//  Create queue variables
MyQueue queue1 = MyQueue();
MyQueue queue2 = MyQueue();
//  Add first node of queue
queue1.enqueue(this->root);
queue2.enqueue(root2);
//  Define tree nodes
TreeNode *node1 = NULL;
TreeNode *node2 = NULL;
// print tree elements
cout << "\n First Tree \n";
this->inorder(this->root);
cout << "\n Second Tree \n";
this->inorder(root2);
//
while (queue1.is_empty() == false || queue2.is_empty() == false)
{
if (status == true)
{
//  Get the front element of both queue
node1 = queue1.peek();
node2 = queue2.peek();
if ((node1 == NULL && node2 != NULL)
|| (node1 != NULL && node2 == NULL)
|| (node1 != NULL && node2 != NULL && node1->data != node2->data))
{
// When both queue front node are not same (That is based on values or null nodes )
status = false;
}
else
{
if (node1->left != NULL)
{
queue1.enqueue(node1->left);
}
if (node1->right != NULL)
{
queue1.enqueue(node1->right);
}
if (node2->right != NULL)
{
queue2.enqueue(node2->right);
}
if (node2->left != NULL)
{
queue2.enqueue(node2->left);
}
queue1.dequeue();
queue2.dequeue();
}
}
else
{
if (queue1.is_empty() == false)
{
queue1.dequeue();
}
if (queue2.is_empty() == false)
{
queue2.dequeue();
}
status = false;
}
}
if (status == false)
{
cout << "\n Anagram not exist \n";
}
else
{
cout << "\n Anagram exist \n";
}
}
};
int main()
{
BinaryTree tree1 = BinaryTree();
BinaryTree tree2 = BinaryTree();
BinaryTree *tree3 = new BinaryTree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
tree1.root = new TreeNode(8);
tree1.root->left = new TreeNode(7);
tree1.root->left->left = new TreeNode(3);
tree1.root->right = new TreeNode(4);
tree1.root->right->left = new TreeNode(9);
tree1.root->right->right = new TreeNode(2);
tree1.root->right->left->left = new TreeNode(5);
tree1.root->right->left->right = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/
tree2.root = new TreeNode(8);
tree2.root->right = new TreeNode(7);
tree2.root->right->right = new TreeNode(3);
tree2.root->left = new TreeNode(4);
tree2.root->left->right = new TreeNode(9);
tree2.root->left->left = new TreeNode(2);
tree2.root->left->right->right = new TreeNode(5);
tree2.root->left->right->left = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------
Third Constructing binary tree
*/
tree3->root = new TreeNode(8);
tree3->root->right = new TreeNode(7);
tree3->root->right->right = new TreeNode(3);
tree3->root->left = new TreeNode(4);
tree3->root->left->right = new TreeNode(6);
tree3->root->left->left = new TreeNode(2);
tree3->root->left->right->right = new TreeNode(9);
tree3->root->left->right->right->right = new TreeNode(5);
// inorder(tree1->root);
//  Test case
tree1.is_anagrams(tree2.root);
tree2.is_anagrams(tree3->root);
return 0;
}``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist``````
``````// Include namespace system
using System;

/*
C# Program
Check if all levels of two trees are anagrams or not
*/

//  Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//  Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//  Queue Node
public class QueueNode
{
public TreeNode element;
public QueueNode next;
public QueueNode(TreeNode element)
{
this.element = element;
this.next = null;
}
}
// Define custom queue class
public class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
// Add a new node at last of queue
public void enqueue(TreeNode element)
{
QueueNode new_node = new QueueNode(element);
if (this.front == null)
{
// When first node of queue
this.front = new_node;
}
else
{
// Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
// Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public Boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
public TreeNode peek()
{
if (is_empty() == false)
{
return this.front.element;
}
else
{
return null;
}
}
}
// Define Binary Tree
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set root of tree
this.root = null;
}
public void inorder(TreeNode node)
{
if (node != null)
{
inorder(node.left);
Console.Write("  " + node.data);
inorder(node.right);
}
}
//  Determine two trees are anagram or not
public void is_anagrams(TreeNode root2)
{
// result indicators
Boolean status = true;
//  Create queue variables
MyQueue queue1 = new MyQueue();
MyQueue queue2 = new MyQueue();
//  Add first node of queue
queue1.enqueue(this.root);
queue2.enqueue(root2);
//  Define tree nodes
TreeNode node1 = null;
TreeNode node2 = null;
// print tree elements
Console.Write("\n First Tree \n");
inorder(this.root);
Console.Write("\n Second Tree \n");
inorder(root2);
//
while (queue1.is_empty() == false || queue2.is_empty() == false)
{
if (status == true)
{
//  Get the front element of both queue
node1 = queue1.peek();
node2 = queue2.peek();
if ((node1 == null && node2 != null) || (node1 != null && node2 == null) || (node1 != null && node2 != null && node1.data != node2.data))
{
// When both queue front node are not same (That is based on values or null nodes )
status = false;
}
else
{
if (node1.left != null)
{
queue1.enqueue(node1.left);
}
if (node1.right != null)
{
queue1.enqueue(node1.right);
}
if (node2.right != null)
{
queue2.enqueue(node2.right);
}
if (node2.left != null)
{
queue2.enqueue(node2.left);
}
queue1.dequeue();
queue2.dequeue();
}
}
else
{
if (queue1.is_empty() == false)
{
queue1.dequeue();
}
if (queue2.is_empty() == false)
{
queue2.dequeue();
}
status = false;
}
}
if (status == false)
{
Console.Write("\n Anagram not exist \n");
}
else
{
Console.Write("\n Anagram exist \n");
}
}
public static void Main(String[] args)
{
BinaryTree tree1 = new BinaryTree();
BinaryTree tree2 = new BinaryTree();
BinaryTree tree3 = new BinaryTree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
tree1.root = new TreeNode(8);
tree1.root.left = new TreeNode(7);
tree1.root.left.left = new TreeNode(3);
tree1.root.right = new TreeNode(4);
tree1.root.right.left = new TreeNode(9);
tree1.root.right.right = new TreeNode(2);
tree1.root.right.left.left = new TreeNode(5);
tree1.root.right.left.right = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/
tree2.root = new TreeNode(8);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(3);
tree2.root.left = new TreeNode(4);
tree2.root.left.right = new TreeNode(9);
tree2.root.left.left = new TreeNode(2);
tree2.root.left.right.right = new TreeNode(5);
tree2.root.left.right.left = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------
Third Constructing binary tree
*/
tree3.root = new TreeNode(8);
tree3.root.right = new TreeNode(7);
tree3.root.right.right = new TreeNode(3);
tree3.root.left = new TreeNode(4);
tree3.root.left.right = new TreeNode(6);
tree3.root.left.left = new TreeNode(2);
tree3.root.left.right.right = new TreeNode(9);
tree3.root.left.right.right.right = new TreeNode(5);
// inorder(tree1->root);
//  Test case
tree1.is_anagrams(tree2.root);
tree2.is_anagrams(tree3.root);
}
}``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist``````
``````<?php
/*
Php Program
Check if all levels of two trees are anagrams or not
*/
//  Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
//  Set node value
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
//  Queue Node
class QueueNode
{
public \$element;
public \$next;

function __construct(\$element)
{
\$this->element = \$element;
\$this->next = null;
}
}
// Define custom queue class
class MyQueue
{
public \$front;
public \$tail;

function __construct()
{
\$this->front = null;
\$this->tail = null;
}
// Add a new node at last of queue
public	function enqueue(\$element)
{
\$new_node = new QueueNode(\$element);
if (\$this->front == null)
{
// When first node of queue
\$this->front = \$new_node;
}
else
{
// Add node at last position
\$this->tail->next = \$new_node;
}
\$this->tail = \$new_node;
}
// Delete first node of queue
public	function dequeue()
{
if (\$this->front != null)
{
if (\$this->tail == \$this->front)
{
\$this->tail = null;
\$this->front = null;
}
else
{
\$this->front = \$this->front->next;
}
}
}
public	function is_empty()
{
if (\$this->front == null)
{
return true;
}
else
{
return false;
}
}
public	function peek()
{
if (\$this->is_empty() == false)
{
return \$this->front->element;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree
{
public \$root;

function __construct()
{
// Set root of tree
\$this->root = null;
}
public	function inorder(\$node)
{
if (\$node != null)
{
\$this->inorder(\$node->left);
echo "  ". \$node->data;
\$this->inorder(\$node->right);
}
}
//  Determine two trees are anagram or not
public	function is_anagrams(\$root2)
{
// result indicators
\$status = true;
//  Create queue variables
\$queue1 = new MyQueue();
\$queue2 = new MyQueue();
//  Add first node of queue
\$queue1->enqueue(\$this->root);
\$queue2->enqueue(\$root2);
//  Define tree nodes
\$node1 = null;
\$node2 = null;
// print tree elements
echo "\n First Tree \n";
\$this->inorder(\$this->root);
echo "\n Second Tree \n";
\$this->inorder(\$root2);
//
while (\$queue1->is_empty() == false || \$queue2->is_empty() == false)
{
if (\$status == true)
{
//  Get the front element of both queue
\$node1 = \$queue1->peek();
\$node2 = \$queue2->peek();
if ((\$node1 == null && \$node2 != null)
|| (\$node1 != null && \$node2 == null)
|| (\$node1 != null && \$node2 != null && \$node1->data != \$node2->data))
{
// When both queue front node are not same (That is based on values or null nodes )
\$status = false;
}
else
{
if (\$node1->left != null)
{
\$queue1->enqueue(\$node1->left);
}
if (\$node1->right != null)
{
\$queue1->enqueue(\$node1->right);
}
if (\$node2->right != null)
{
\$queue2->enqueue(\$node2->right);
}
if (\$node2->left != null)
{
\$queue2->enqueue(\$node2->left);
}
\$queue1->dequeue();
\$queue2->dequeue();
}
}
else
{
if (\$queue1->is_empty() == false)
{
\$queue1->dequeue();
}
if (\$queue2->is_empty() == false)
{
\$queue2->dequeue();
}
\$status = false;
}
}
if (\$status == false)
{
echo "\n Anagram not exist \n";
}
else
{
echo "\n Anagram exist \n";
}
}
}

function main()
{
\$tree1 = new BinaryTree();
\$tree2 = new BinaryTree();
\$tree3 = new BinaryTree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
\$tree1->root = new TreeNode(8);
\$tree1->root->left = new TreeNode(7);
\$tree1->root->left->left = new TreeNode(3);
\$tree1->root->right = new TreeNode(4);
\$tree1->root->right->left = new TreeNode(9);
\$tree1->root->right->right = new TreeNode(2);
\$tree1->root->right->left->left = new TreeNode(5);
\$tree1->root->right->left->right = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/
\$tree2->root = new TreeNode(8);
\$tree2->root->right = new TreeNode(7);
\$tree2->root->right->right = new TreeNode(3);
\$tree2->root->left = new TreeNode(4);
\$tree2->root->left->right = new TreeNode(9);
\$tree2->root->left->left = new TreeNode(2);
\$tree2->root->left->right->right = new TreeNode(5);
\$tree2->root->left->right->left = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------
Third Constructing binary tree
*/
\$tree3->root = new TreeNode(8);
\$tree3->root->right = new TreeNode(7);
\$tree3->root->right->right = new TreeNode(3);
\$tree3->root->left = new TreeNode(4);
\$tree3->root->left->right = new TreeNode(6);
\$tree3->root->left->left = new TreeNode(2);
\$tree3->root->left->right->right = new TreeNode(9);
\$tree3->root->left->right->right->right = new TreeNode(5);
// inorder(tree1->root);
//  Test case
\$tree1->is_anagrams(\$tree2->root);
\$tree2->is_anagrams(\$tree3->root);
}
main();``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist``````
``````/*
Node Js Program
Check if all levels of two trees are anagrams or not
*/
//  Binary Tree node
class TreeNode
{
constructor(data)
{
//  Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
//  Queue Node
class QueueNode
{
constructor(element)
{
this.element = element;
this.next = null;
}
}
// Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.tail = null;
}
// Add a new node at last of queue
enqueue(element)
{
var new_node = new QueueNode(element);
if (this.front == null)
{
// When first node of queue
this.front = new_node;
}
else
{
// Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
// Delete first node of queue
dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
peek()
{
if (this.is_empty() == false)
{
return this.front.element;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree
{
constructor()
{
// Set root of tree
this.root = null;
}
inorder(node)
{
if (node != null)
{
this.inorder(node.left);
process.stdout.write("  " + node.data);
this.inorder(node.right);
}
}
//  Determine two trees are anagram or not
is_anagrams(root2)
{
// result indicators
var status = true;
//  Create queue variables
var queue1 = new MyQueue();
var queue2 = new MyQueue();
//  Add first node of queue
queue1.enqueue(this.root);
queue2.enqueue(root2);
//  Define tree nodes
var node1 = null;
var node2 = null;
// print tree elements
process.stdout.write("\n First Tree \n");
this.inorder(this.root);
process.stdout.write("\n Second Tree \n");
this.inorder(root2);
//
while (queue1.is_empty() == false || queue2.is_empty() == false)
{
if (status == true)
{
//  Get the front element of both queue
node1 = queue1.peek();
node2 = queue2.peek();
if ((node1 == null && node2 != null)
|| (node1 != null && node2 == null)
|| (node1 != null && node2 != null && node1.data != node2.data))
{
// When both queue front node are not same (That is based on values or null nodes )
status = false;
}
else
{
if (node1.left != null)
{
queue1.enqueue(node1.left);
}
if (node1.right != null)
{
queue1.enqueue(node1.right);
}
if (node2.right != null)
{
queue2.enqueue(node2.right);
}
if (node2.left != null)
{
queue2.enqueue(node2.left);
}
queue1.dequeue();
queue2.dequeue();
}
}
else
{
if (queue1.is_empty() == false)
{
queue1.dequeue();
}
if (queue2.is_empty() == false)
{
queue2.dequeue();
}
status = false;
}
}
if (status == false)
{
process.stdout.write("\n Anagram not exist \n");
}
else
{
process.stdout.write("\n Anagram exist \n");
}
}
}

function main()
{
var tree1 = new BinaryTree();
var tree2 = new BinaryTree();
var tree3 = new BinaryTree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
tree1.root = new TreeNode(8);
tree1.root.left = new TreeNode(7);
tree1.root.left.left = new TreeNode(3);
tree1.root.right = new TreeNode(4);
tree1.root.right.left = new TreeNode(9);
tree1.root.right.right = new TreeNode(2);
tree1.root.right.left.left = new TreeNode(5);
tree1.root.right.left.right = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/
tree2.root = new TreeNode(8);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(3);
tree2.root.left = new TreeNode(4);
tree2.root.left.right = new TreeNode(9);
tree2.root.left.left = new TreeNode(2);
tree2.root.left.right.right = new TreeNode(5);
tree2.root.left.right.left = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------------------
Third Constructing binary tree
*/
tree3.root = new TreeNode(8);
tree3.root.right = new TreeNode(7);
tree3.root.right.right = new TreeNode(3);
tree3.root.left = new TreeNode(4);
tree3.root.left.right = new TreeNode(6);
tree3.root.left.left = new TreeNode(2);
tree3.root.left.right.right = new TreeNode(9);
tree3.root.left.right.right.right = new TreeNode(5);

//  Test case
tree1.is_anagrams(tree2.root);
tree2.is_anagrams(tree3.root);
}
main();``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist``````
``````#  Python 3 Program
#  Check if all levels of two trees are anagrams or not

#  Binary Tree node
class TreeNode :

def __init__(self, data) :
#  Set node value
self.data = data
self.left = None
self.right = None

#  Queue Node
class QueueNode :

def __init__(self, element) :
self.element = element
self.next = None

# Define custom queue class
class MyQueue :

def __init__(self) :
self.front = None
self.tail = None

# Add a new node at last of queue
def enqueue(self, element) :
new_node = QueueNode(element)
if (self.front == None) :
# When first node of queue
self.front = new_node
else :
# Add node at last position
self.tail.next = new_node

self.tail = new_node

# Delete first node of queue
def dequeue(self) :
if (self.front != None) :
if (self.tail == self.front) :
self.tail = None
self.front = None
else :
self.front = self.front.next

def is_empty(self) :
if (self.front == None) :
return True
else :
return False

def peek(self) :
if (self.is_empty() == False) :
return self.front.element
else :
return None

# Define Binary Tree
class BinaryTree :

def __init__(self) :
# Set root of tree
self.root = None

def inorder(self, node) :
if (node != None) :
self.inorder(node.left)
print("  ", node.data, end = "")
self.inorder(node.right)

#  Determine two trees are anagram or not
def is_anagrams(self, root2) :
# result indicators
status = True
#  Create queue variables
queue1 = MyQueue()
queue2 = MyQueue()
#  Add first node of queue
queue1.enqueue(self.root)
queue2.enqueue(root2)
#  Define tree nodes
node1 = None
node2 = None
# print tree elements
print("\n First Tree \n", end = "")
self.inorder(self.root)
print("\n Second Tree \n", end = "")
self.inorder(root2)
#
while (queue1.is_empty() == False or queue2.is_empty() == False) :
if (status == True) :
#  Get the front element of both queue
node1 = queue1.peek()
node2 = queue2.peek()
if ((node1 == None and node2 != None) or(node1 != None and node2 == None) or(node1 != None and node2 != None and node1.data != node2.data)) :
# When both queue front node are not same (That is based on values or null nodes )
status = False
else :
if (node1.left != None) :
queue1.enqueue(node1.left)

if (node1.right != None) :
queue1.enqueue(node1.right)

if (node2.right != None) :
queue2.enqueue(node2.right)

if (node2.left != None) :
queue2.enqueue(node2.left)

queue1.dequeue()
queue2.dequeue()

else :
if (queue1.is_empty() == False) :
queue1.dequeue()

if (queue2.is_empty() == False) :
queue2.dequeue()

status = False

if (status == False) :
print("\n Anagram not exist \n", end = "")
else :
print("\n Anagram exist \n", end = "")

def main() :
tree1 = BinaryTree()
tree2 = BinaryTree()
tree3 = BinaryTree()
#
#              8
#            /   \
#           7     4
#          /     /  \
#         3     9    2
#              / \
#             5   6
#         ------------------
#         Constructing binary tree
#

tree1.root = TreeNode(8)
tree1.root.left = TreeNode(7)
tree1.root.left.left = TreeNode(3)
tree1.root.right = TreeNode(4)
tree1.root.right.left = TreeNode(9)
tree1.root.right.right = TreeNode(2)
tree1.root.right.left.left = TreeNode(5)
tree1.root.right.left.right = TreeNode(6)
#
#              8
#            /   \
#           4     7
#          /  \    \
#         2    9    3
#             / \
#            6   5
#         -----------------
#         Second Constructing binary tree
#

tree2.root = TreeNode(8)
tree2.root.right = TreeNode(7)
tree2.root.right.right = TreeNode(3)
tree2.root.left = TreeNode(4)
tree2.root.left.right = TreeNode(9)
tree2.root.left.left = TreeNode(2)
tree2.root.left.right.right = TreeNode(5)
tree2.root.left.right.left = TreeNode(6)
#
#              8
#            /   \
#           4     7
#          /  \    \
#         2    6    3
#               \
#                9
#                 \
#                  5
#          -----------------
#         Third Constructing binary tree
#

tree3.root = TreeNode(8)
tree3.root.right = TreeNode(7)
tree3.root.right.right = TreeNode(3)
tree3.root.left = TreeNode(4)
tree3.root.left.right = TreeNode(6)
tree3.root.left.left = TreeNode(2)
tree3.root.left.right.right = TreeNode(9)
tree3.root.left.right.right.right = TreeNode(5)
#  Test case
tree1.is_anagrams(tree2.root)
tree2.is_anagrams(tree3.root)

if __name__ == "__main__": main()``````

#### Output

`````` First Tree
3   7   8   5   9   6   4   2
Second Tree
2   4   6   9   5   8   7   3
Anagram exist

First Tree
2   4   6   9   5   8   7   3
Second Tree
2   4   6   9   5   8   7   3
Anagram not exist``````
``````#  Ruby Program
#  Check if all levels of two trees are anagrams or not

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right

def initialize(data)
#  Set node value
self.data = data
self.left = nil
self.right = nil
end

end

#  Queue Node
class QueueNode
# Define the accessor and reader of class QueueNode
attr_accessor :element, :next

def initialize(element)
self.element = element
self.next = nil
end

end

# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :front, :tail

def initialize()
self.front = nil
self.tail = nil
end

# Add a new node at last of queue
def enqueue(element)
new_node = QueueNode.new(element)
if (self.front == nil)
# When first node of queue
self.front = new_node
else
# Add node at last position
self.tail.next = new_node
end

self.tail = new_node
end

# Delete first node of queue
def dequeue()
if (self.front != nil)
if (self.tail == self.front)
self.tail = nil
self.front = nil
else
self.front = self.front.next
end

end

end

def is_empty()
if (self.front == nil)
return true
else
return false
end

end

def peek()
if (self.is_empty() == false)
return self.front.element
else
return nil
end

end

end

# Define Binary Tree
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root

def initialize()
# Set root of tree
self.root = nil
end

def inorder(node)
if (node != nil)
self.inorder(node.left)
print("  ", node.data)
self.inorder(node.right)
end

end

#  Determine two trees are anagram or not
def is_anagrams(root2)
# result indicators
status = true
#  Create queue variables
queue1 = MyQueue.new()
queue2 = MyQueue.new()
#  Add first node of queue
queue1.enqueue(self.root)
queue2.enqueue(root2)
#  Define tree nodes
node1 = nil
node2 = nil
# print tree elements
print("\n First Tree \n")
self.inorder(self.root)
print("\n Second Tree \n")
self.inorder(root2)
#
while (queue1.is_empty() == false || queue2.is_empty() == false)
if (status == true)
#  Get the front element of both queue
node1 = queue1.peek()
node2 = queue2.peek()
if ((node1 == nil && node2 != nil) || (node1 != nil && node2 == nil) || (node1 != nil && node2 != nil && node1.data != node2.data))
# When both queue front node are not same (That is based on values or null nodes )
status = false
else
if (node1.left != nil)
queue1.enqueue(node1.left)
end

if (node1.right != nil)
queue1.enqueue(node1.right)
end

if (node2.right != nil)
queue2.enqueue(node2.right)
end

if (node2.left != nil)
queue2.enqueue(node2.left)
end

queue1.dequeue()
queue2.dequeue()
end

else
if (queue1.is_empty() == false)
queue1.dequeue()
end

if (queue2.is_empty() == false)
queue2.dequeue()
end

status = false
end

end

if (status == false)
print("\n Anagram not exist \n")
else
print("\n Anagram exist \n")
end

end

end

def main()
tree1 = BinaryTree.new()
tree2 = BinaryTree.new()
tree3 = BinaryTree.new()
#
#              8
#            /   \
#           7     4
#          /     /  \
#         3     9    2
#              / \
#             5   6
#         ------------------
#         Constructing binary tree
#

tree1.root = TreeNode.new(8)
tree1.root.left = TreeNode.new(7)
tree1.root.left.left = TreeNode.new(3)
tree1.root.right = TreeNode.new(4)
tree1.root.right.left = TreeNode.new(9)
tree1.root.right.right = TreeNode.new(2)
tree1.root.right.left.left = TreeNode.new(5)
tree1.root.right.left.right = TreeNode.new(6)
#
#              8
#            /   \
#           4     7
#          /  \    \
#         2    9    3
#             / \
#            6   5
#         -----------------
#         Second Constructing binary tree
#

tree2.root = TreeNode.new(8)
tree2.root.right = TreeNode.new(7)
tree2.root.right.right = TreeNode.new(3)
tree2.root.left = TreeNode.new(4)
tree2.root.left.right = TreeNode.new(9)
tree2.root.left.left = TreeNode.new(2)
tree2.root.left.right.right = TreeNode.new(5)
tree2.root.left.right.left = TreeNode.new(6)
#
#              8
#            /   \
#           4     7
#          /  \    \
#         2    6    3
#               \
#                9
#                 \
#                  5
#          -----------------
#         Third Constructing binary tree
#

tree3.root = TreeNode.new(8)
tree3.root.right = TreeNode.new(7)
tree3.root.right.right = TreeNode.new(3)
tree3.root.left = TreeNode.new(4)
tree3.root.left.right = TreeNode.new(6)
tree3.root.left.left = TreeNode.new(2)
tree3.root.left.right.right = TreeNode.new(9)
tree3.root.left.right.right.right = TreeNode.new(5)
#  Test case
tree1.is_anagrams(tree2.root)
tree2.is_anagrams(tree3.root)
end

main()``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist
``````
``````/*
Scala Program
Check if all levels of two trees are anagrams or not
*/

//  Binary Tree node
class TreeNode(var data: Int , var left: TreeNode , var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
//  Queue Node
class QueueNode(var element: TreeNode , var next: QueueNode)
{
def this(element: TreeNode)
{
this(element, null);
}
}
// Define custom queue class
class MyQueue(var front: QueueNode , var tail: QueueNode)
{
def this()
{
this(null, null);
}
// Add a new node at last of queue
def enqueue(element: TreeNode): Unit = {
var new_node: QueueNode = new QueueNode(element);
if (this.front == null)
{
// When first node of queue
this.front = new_node;
}
else
{
// Add node at last position
this.tail.next = new_node;
}
this.tail = new_node;
}
// Delete first node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
def is_empty(): Boolean = {
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
def peek(): TreeNode = {
if (is_empty() == false)
{
return this.front.element;
}
else
{
return null;
}
}
}
// Define Binary Tree
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def inorder(node: TreeNode): Unit = {
if (node != null)
{
inorder(node.left);
print("  " + node.data);
inorder(node.right);
}
}
//  Determine two trees are anagram or not
def is_anagrams(root2: TreeNode): Unit = {
// result indicators
var status: Boolean = true;
//  Create queue variables
var queue1: MyQueue = new MyQueue();
var queue2: MyQueue = new MyQueue();
//  Add first node of queue
queue1.enqueue(this.root);
queue2.enqueue(root2);
//  Define tree nodes
var node1: TreeNode = null;
var node2: TreeNode = null;
// print tree elements
print("\n First Tree \n");
inorder(this.root);
print("\n Second Tree \n");
inorder(root2);
//
while (queue1.is_empty() == false || queue2.is_empty() == false)
{
if (status == true)
{
//  Get the front element of both queue
node1 = queue1.peek();
node2 = queue2.peek();
if ((node1 == null && node2 != null) || (node1 != null && node2 == null) || (node1 != null && node2 != null && node1.data != node2.data))
{
// When both queue front node are not same (That is based on values or null nodes )
status = false;
}
else
{
if (node1.left != null)
{
queue1.enqueue(node1.left);
}
if (node1.right != null)
{
queue1.enqueue(node1.right);
}
if (node2.right != null)
{
queue2.enqueue(node2.right);
}
if (node2.left != null)
{
queue2.enqueue(node2.left);
}
queue1.dequeue();
queue2.dequeue();
}
}
else
{
if (queue1.is_empty() == false)
{
queue1.dequeue();
}
if (queue2.is_empty() == false)
{
queue2.dequeue();
}
status = false;
}
}
if (status == false)
{
print("\n Anagram not exist \n");
}
else
{
print("\n Anagram exist \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree1: BinaryTree = new BinaryTree();
var tree2: BinaryTree = new BinaryTree();
var tree3: BinaryTree = new BinaryTree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
tree1.root = new TreeNode(8);
tree1.root.left = new TreeNode(7);
tree1.root.left.left = new TreeNode(3);
tree1.root.right = new TreeNode(4);
tree1.root.right.left = new TreeNode(9);
tree1.root.right.right = new TreeNode(2);
tree1.root.right.left.left = new TreeNode(5);
tree1.root.right.left.right = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/
tree2.root = new TreeNode(8);
tree2.root.right = new TreeNode(7);
tree2.root.right.right = new TreeNode(3);
tree2.root.left = new TreeNode(4);
tree2.root.left.right = new TreeNode(9);
tree2.root.left.left = new TreeNode(2);
tree2.root.left.right.right = new TreeNode(5);
tree2.root.left.right.left = new TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------
Third Constructing binary tree
*/
tree3.root = new TreeNode(8);
tree3.root.right = new TreeNode(7);
tree3.root.right.right = new TreeNode(3);
tree3.root.left = new TreeNode(4);
tree3.root.left.right = new TreeNode(6);
tree3.root.left.left = new TreeNode(2);
tree3.root.left.right.right = new TreeNode(9);
tree3.root.left.right.right.right = new TreeNode(5);
//  Test case
tree1.is_anagrams(tree2.root);
tree2.is_anagrams(tree3.root);
}
}``````

#### Output

`````` First Tree
3  7  8  5  9  6  4  2
Second Tree
2  4  6  9  5  8  7  3
Anagram exist

First Tree
2  4  6  9  5  8  7  3
Second Tree
2  4  6  9  5  8  7  3
Anagram not exist``````
``````/*
Swift 4 Program
Check if all levels of two trees are anagrams or not
*/

//  Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
//  Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
//  Queue Node
class QueueNode
{
var element: TreeNode? ;
var next: QueueNode? ;
init(_ element: TreeNode? )
{
self.element = element;
self.next = nil;
}
}
// Define custom queue class
class MyQueue
{
var front: QueueNode? ;
var tail: QueueNode? ;
init()
{
self.front = nil;
self.tail = nil;
}
// Add a new node at last of queue
func enqueue(_ element: TreeNode? )
{
let new_node: QueueNode? = QueueNode(element);
if (self.front == nil)
{
// When first node of queue
self.front = new_node;
}
else
{
// Add node at last position
self.tail!.next = new_node;
}
self.tail = new_node;
}
// Delete first node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.tail === self.front)
{
self.tail = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
}
}
func is_empty()->Bool
{
if (self.front == nil)
{
return true;
}
else
{
return false;
}
}
func peek()->TreeNode?
{
if (self.is_empty() == false)
{
return self.front!.element;
}
else
{
return nil;
}
}
}
// Define Binary Tree
class BinaryTree
{
var root: TreeNode? ;
init()
{
// Set root of tree
self.root = nil;
}
func inorder(_ node: TreeNode? )
{
if (node != nil)
{
self.inorder(node!.left);
print("  ", node!.data, terminator: "");
self.inorder(node!.right);
}
}
//  Determine two trees are anagram or not
func is_anagrams(_ root2: TreeNode? )
{
// result indicators
var status: Bool = true;
//  Create queue variables
let queue1: MyQueue = MyQueue();
let queue2: MyQueue = MyQueue();
//  Add first node of queue
queue1.enqueue(self.root);
queue2.enqueue(root2);
//  Define tree nodes
var node1: TreeNode? = nil;
var node2: TreeNode? = nil;
// print tree elements
print("\n First Tree \n", terminator: "");
self.inorder(self.root);
print("\n Second Tree \n", terminator: "");
self.inorder(root2);
//
while (queue1.is_empty() == false || queue2.is_empty() == false)
{
if (status == true)
{
//  Get the front element of both queue
node1 = queue1.peek();
node2 = queue2.peek();
if ((node1 == nil && node2 != nil) || (node1 != nil && node2 == nil) || (node1 != nil && node2 != nil && node1!.data != node2!.data))
{
// When both queue front node are not same (That is based on values or null nodes )
status = false;
}
else
{
if (node1!.left != nil)
{
queue1.enqueue(node1!.left);
}
if (node1!.right != nil)
{
queue1.enqueue(node1!.right);
}
if (node2!.right != nil)
{
queue2.enqueue(node2!.right);
}
if (node2!.left != nil)
{
queue2.enqueue(node2!.left);
}
queue1.dequeue();
queue2.dequeue();
}
}
else
{
if (queue1.is_empty() == false)
{
queue1.dequeue();
}
if (queue2.is_empty() == false)
{
queue2.dequeue();
}
status = false;
}
}
if (status == false)
{
print("\n Anagram not exist \n", terminator: "");
}
else
{
print("\n Anagram exist \n", terminator: "");
}
}
}
func main()
{
let tree1: BinaryTree = BinaryTree();
let tree2: BinaryTree = BinaryTree();
let tree3: BinaryTree? = BinaryTree();
/*
8
/   \
7     4
/     /  \
3     9    2
/ \
5   6
------------------
Constructing binary tree
*/
tree1.root = TreeNode(8);
tree1.root!.left = TreeNode(7);
tree1.root!.left!.left = TreeNode(3);
tree1.root!.right = TreeNode(4);
tree1.root!.right!.left = TreeNode(9);
tree1.root!.right!.right = TreeNode(2);
tree1.root!.right!.left!.left = TreeNode(5);
tree1.root!.right!.left!.right = TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    9    3
/ \
6   5
-----------------
Second Constructing binary tree
*/
tree2.root = TreeNode(8);
tree2.root!.right = TreeNode(7);
tree2.root!.right!.right = TreeNode(3);
tree2.root!.left = TreeNode(4);
tree2.root!.left!.right = TreeNode(9);
tree2.root!.left!.left = TreeNode(2);
tree2.root!.left!.right!.right = TreeNode(5);
tree2.root!.left!.right!.left = TreeNode(6);
/*
8
/   \
4     7
/  \    \
2    6    3
\
9
\
5
-----------------
Third Constructing binary tree
*/
tree3!.root = TreeNode(8);
tree3!.root!.right = TreeNode(7);
tree3!.root!.right!.right = TreeNode(3);
tree3!.root!.left = TreeNode(4);
tree3!.root!.left!.right = TreeNode(6);
tree3!.root!.left!.left = TreeNode(2);
tree3!.root!.left!.right!.right = TreeNode(9);
tree3!.root!.left!.right!.right!.right = TreeNode(5);
//  Test case
tree1.is_anagrams(tree2.root);
tree2.is_anagrams(tree3!.root);
}
main();``````

#### Output

`````` First Tree
3   7   8   5   9   6   4   2
Second Tree
2   4   6   9   5   8   7   3
Anagram exist

First Tree
2   4   6   9   5   8   7   3
Second Tree
2   4   6   9   5   8   7   3
Anagram not exist``````

## Output Explanation

The code implements the algorithm and determines whether all levels of two given binary trees are anagrams or not. It first constructs three binary trees, then checks the anagram property for each pair of trees and prints whether they are anagrams or not.

## Time Complexity

The time complexity of this algorithm depends on the level-order traversal of the trees. If there are N nodes in each tree, the time complexity is O(N). The space complexity is also O(N), as we are using queues for both trees.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post