-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFind the maximum depth or height of the tree
110 lines (108 loc) · 2.76 KB
/
Find the maximum depth or height of the tree
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
Implement a C program to find the maximum depth or height of the tree.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct tree{
int data;
struct tree *left;
struct tree *right;
};
struct queue{
int front,rear;
int size;
struct tree* *array;
};
struct tree *newNode(int data){
struct tree *t=(struct tree*)malloc(sizeof(struct tree));
t->data = data;
t->left = t->right = NULL;
return t;
}
struct queue* createqueue(int size){
struct queue *queue = (struct queue*)malloc(sizeof(struct queue));
queue->size = size;
queue->front = 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 *t = queue->array[queue->front];
if(queue->front==queue->rear)
queue->front = queue->rear = -1;
else
queue->front++;
return t;
}
void insert(struct tree **root,int data,struct queue* queue){
struct tree *t = newNode(data);
if(*root == NULL)
*root = t;
else{
struct tree *front = queue->array[queue->front];
if(front->left==NULL)
front->left = t;
else if(front->right==NULL)
front->right = t;
if(front->left!=NULL && front->right!=NULL)
dequeue(queue);
}
enqueue(t,queue);
}
/*void inorder(struct tree *t){
inorder(t->left);
printf(" %d",t->data);
inorder(t->right);
}
void preorder(struct tree *t){
printf(" %d",t->data);
preorder(t->left);
preorder(t->right);
}
void postorder(struct tree *t){
postorder(t->left);
postorder(t->right);
printf(" %d",t->data);
}
*/int max(int a,int b){
if(a>b) return a;
else return b;
}
int maxDepth(struct tree *root){
if(root == NULL)
return 0;
else
return max(1+maxDepth(root->left),1+maxDepth(root->right));
}
int main()
{
struct tree* root=NULL;
char ans[3];
int data;
struct queue* queue = createqueue(50);
do{
printf("Enter the element to be inserted in the tree\n");
scanf("%d",&data);
insert(&root,data,queue);
printf("Do you want to insert another element?\n");
scanf("%s",ans);
}while(strcmp(ans,"yes")==0);
/*printf("Inorder Traversal : The elements in the tree are");
inorder(root);
printf("\n");
printf("Preorder Traversal : The elements in the tree are");
preorder(root);
printf("\n");
printf("Postorder Traversal : The elements in the tree are");
postorder(root);
*/ printf("Hight of tree is %d",maxDepth(root));
return 0;
}