-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDetermine if two trees are identical
119 lines (110 loc) · 3.02 KB
/
Determine if two trees are identical
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
Implement a C program to find the two trees are identical or not. Two trees are identical when they have same data and arrangement of data is also same.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct tree{
int data;
struct tree *right,*left;
};
struct queue{
int front,rear;
int size;
struct tree**array;
};
struct tree* newNode(int data){
struct tree *nn = (struct tree*)malloc(sizeof(struct tree));
nn->data = data;
nn->left = NULL;
nn->right = NULL;
return nn;
}
struct queue* createQueue(int size){
struct queue* queue = (struct queue*)malloc(sizeof(struct queue));
queue->size = size;
queue->front = -1;
queue->rear = -1;
queue->array = (struct tree**)malloc(size*sizeof(struct tree*));
return queue;
}
void enqueue(struct tree *root, struct queue* queue){
if(queue->rear==queue->size-1)
return;
queue->array[++queue->rear] = root;
if(queue->front == -1)
queue->front++;
}
struct tree* dequeue(struct queue* queue){
if(queue->front==-1)
return NULL;
struct tree *temp = queue->array[queue->front];
if(queue->front==queue->rear)
queue->rear = queue->front = -1;
else
queue->front++;
return temp;
}
void insert(struct tree **root, int data, struct queue* queue){
struct tree *temp = newNode(data);
if(*root == NULL)
*root = temp;
else{
struct tree *front = queue->array[queue->front];
if(front->left==NULL)
front->left = temp;
else if(front->right == NULL)
front->right = temp;
if(front->left!=NULL && front->right!=NULL)
dequeue(queue);
}
enqueue(temp,queue);
}
int identicalTrees(struct tree *a,struct tree *b){
if(a==NULL && b==NULL){
return 1;
}
else if((a==NULL && b!=NULL)||(a!=NULL && b==NULL)){
return 0;
}
else{
if((a->data==b->data)&&(identicalTrees(a->left,b->left))&&(identicalTrees(a->right,b->right))){
return 1;
}
else{
return 0;
}
}
}
int main()
{
struct tree* root1 = NULL,*root2=NULL;
char ans[3];
int data,dec;
struct queue* queue1 = createQueue(50),*queue2=createQueue(50);
do
{
printf("Data to be inserted in 1st tree or 2nd tree?");
scanf("%d",&dec);
switch(dec){
case 1:{printf("Enter the element to be inserted in the 1st tree\n");
scanf("%d",&data);
insert(&root1, data, queue1);
break;
}
case 2:{
printf("Enter the element to be inserted in the 2nd tree\n");
scanf("%d",&data);
insert(&root2, data, queue2);
break;
}
}
printf("Do you want to insert element?\n");
scanf("%s",ans);
} while (strcmp(ans,"yes") ==0);
if(identicalTrees(root1,root2)){
printf("Both tree are identical.");
}
else{
printf("Trees are not identical.");
}
return 0;
}