-
Notifications
You must be signed in to change notification settings - Fork 0
/
Program to Find if the given Binary Tree is complete
143 lines (120 loc) · 3.54 KB
/
Program to Find if the given Binary Tree is complete
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_Q_SIZE 500
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* function prototypes for functions needed for Queue data
structure. A queue is needed for level order tarversal */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);
bool isQueueEmpty(int *front, int *rear);
/* Given a binary tree, return true if the tree is complete
else false */
bool isCompleteBT(struct node* root)
{
// Base Case: An empty tree is complete Binary Tree
if (root == NULL)
return true;
// Create an empty queue
int rear, front;
struct node **queue = createQueue(&front, &rear);
// Create a flag variable which will be set true
// when a non full node is seen
bool flag = false;
// Do level order traversal using queue.
enQueue(queue, &rear, root);
while(!isQueueEmpty(&front, &rear))
{
struct node *temp_node = deQueue(queue, &front);
/* Check if left child is present*/
if(temp_node->left)
{
// If we have seen a non full node, and we see a node
// with non-empty left child, then the given tree is not
// a complete Binary Tree
if (flag == true)
return false;
enQueue(queue, &rear, temp_node->left); // Enqueue Left Child
}
else // If this a non-full node, set the flag as true
flag = true;
/* Check if right child is present*/
if(temp_node->right)
{
// If we have seen a non full node, and we see a node
// with non-empty right child, then the given tree is not
// a complete Binary Tree
if(flag == true)
return false;
enQueue(queue, &rear, temp_node->right); // Enqueue Right Child
}
else // If this a non-full node, set the flag as true
flag = true;
}
// If we reach here, then the tree is complete Bianry Tree
return true;
}
/*UTILITY FUNCTIONS*/
struct node** createQueue(int *front, int *rear)
{
struct node **queue =
(struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);
*front = *rear = 0;
return queue;
}
void enQueue(struct node **queue, int *rear, struct node *new_node)
{
queue[*rear] = new_node;
(*rear)++;
}
struct node *deQueue(struct node **queue, int *front)
{
(*front)++;
return queue[*front - 1];
}
bool isQueueEmpty(int *front, int *rear)
{
return (*rear == *front);
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* Driver program to test above functions*/
int main()
{
/* Let us construct the following Binary Tree which
is not a complete Binary Tree
1
/
2 3
/
4 5 6
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->right = newNode(6);
if ( isCompleteBT(root) == true )
printf ("Complete Binary Tree");
else
printf ("NOT Complete Binary Tree");
return 0;
}