Check whether a given binary tree is complete or not

/*
    C Program 
    Check whether a given binary tree is complete 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 *makeQueue()
{
	// Create dynamic node of MyQueue
	struct MyQueue *node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
	if (node == NULL)
	{
		printf("\n Memory Overflow, when creating a new Queue\n");
	}
	else
	{
		node->front = NULL;
		node->tail = NULL;
	}
	return node;
}
// Returns a new node of tree
struct TreeNode *newNode(int data)
{
	// Create dynamic node
	struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
	if (node != NULL)
	{
		//Set data and pointer values
		node->data = data;
		node->left = NULL;
		node->right = NULL;
	}
	else
	{
		//This is indicates, segmentation fault or memory overflow problem
		printf("Memory Overflow\n");
	}
	//return new node
	return node;
}
struct BinaryTree *makeTree()
{
	// 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 isEmpty(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 (isEmpty(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 (isEmpty(queue) == 1)
	{
		return NULL;
	}
	else
	{
		return queue->front->element;
	}
}
// Display tree elements
void inorder(struct TreeNode *node)
{
	if (node != NULL)
	{
		inorder(node->left);
		printf("  %d", node->data);
		inorder(node->right);
	}
}
// Determine whether given binary tree is complete binary tree or not
void isCompleteTree(struct BinaryTree *tree)
{
	int status = 0;
	struct TreeNode *node = tree->root;
	if (node == NULL)
	{
		// When tree is empty
		status = 1;
	}
	else
	{
		// Assume that initial tree is complete tree
		status = 1;
		// This is used to track missing child nodes
		int tracker = 0;
		// Create a queue
		struct MyQueue *q = makeQueue();
		// Add first node of tree
		enqueue(q, node);
		// Execute loop until queue is not empty
		while (node != NULL)
		{
			if (status == 1)
			{
				if (node->left != NULL && node->right != NULL)
				{
					if (tracker > 0)
					{
						// When already missing one child or
						// We already reached a leaf node
						status = 0;
					}
					else
					{
						// When both child exist
						enqueue(q, node->left);
						enqueue(q, node->right);
					}
				}
				else if (node->left != NULL || node->right != NULL)
				{
					// When one child exists
					tracker++;
					if (tracker == 1)
					{
						if (node->right != NULL)
						{
							// Because left subtree are empty
							status = 0;
						}
						else
						{
							// Allow first time left subtree 
							enqueue(q, node->left);
						}
					}
					else
					{
						// When more than one child nodes are missing
						status = 0;
					}
				}
				else
				{
					// Get a leaf node
					tracker = 1;
				}
			}
			// Remove a queue element
			dequeue(q);
			// Get front element of queue
			node = peek(q);
		}
		// Display tree elements
		inorder(tree->root);
		if (status == 1)
		{
			printf("\n  Complete Binary Tree\n");
		}
		else
		{
			printf("\n  Not a Complete Binary Tree\n");
		}
	}
}
int main(int argc, char
	const *argv[])
{
	// Define tree
	struct BinaryTree *tree = makeTree();
	/*
              1
            /   \
           2     3
         /   \     
        4     5  
       / \   / \
      6   7 8   9
  
    -----------------------
        Binary Tree
    -----------------------
    */
	tree->root = newNode(1);
	tree->root->left = newNode(2);
	tree->root->right = newNode(3);
	tree->root->left->left = newNode(4);
	tree->root->left->right = newNode(5);
	tree->root->left->left->left = newNode(6);
	tree->root->left->left->right = newNode(7);
	tree->root->left->right->left = newNode(8);
	tree->root->left->right->right = newNode(9);
	isCompleteTree(tree);
	tree->root->right->left = newNode(-1);
	tree->root->right->right = newNode(-2);
	/*
    After add new nodes : -1,-2
    -----------------

               1
              /  \ 
             /    \  
            /      \
           2        3
         /   \     / \  
        4     5  -1  -2
       / \   / \
      6   7 8   9
  
    -----------------------
        Binary Tree
    -----------------------
    */
	isCompleteTree(tree);
	return 0;
}

Output

  6  4  7  2  8  5  9  1  3
  Not a Complete Binary Tree
  6  4  7  2  8  5  9  1  -1  3  -2
  Complete Binary Tree