#include<stdio.h>
#include<malloc.h>
struct binaryTreeNode{
int data;
struct binaryTreeNode * left;
struct binaryTreeNode * right;
};
struct node
{
struct binaryTreeNode * data;
struct node * next;
};
struct queue
{
struct node * front;
struct node * rear;
};
struct queue * enQueue(struct queue * q, struct binaryTreeNode * num)
{
struct node * temp = (struct node*)malloc(sizeof(struct node));
temp -> data = num;
temp -> next = NULL;
if(q == NULL)
{
q = (struct queue*)malloc(sizeof(struct queue));
q -> front = temp;
}
else
q -> rear -> next = temp;
q -> rear = temp;
//Code obtained from http://w...content-available-to-author-only...s.com
//Feel free to copy but please acknowledge the site wherever possible
return q;
}
struct queue * deQueue(struct queue * q)
{
struct node * temp = q->front;
q -> front = q->front->next;
free(temp);
if(q->front == NULL)
return NULL;
else
return q;
}
int isQueueEmpty(struct queue * q)
{
if(q)
return 0;
else
return 1;
}
// A function to insert a number in a binary tree
// Parameters - the root node and the number to insert
struct binaryTreeNode * insertInBinaryTree(struct binaryTreeNode * root, int num)
{
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;
// Create a new node to insert
struct binaryTreeNode * newNode = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
// Assign the values to this new node
newNode -> data = num;
newNode -> left = NULL;
newNode -> right = NULL;
if(root == NULL)
{
// If the root is NULL then the newNode is inserted at root
root = newNode;
return root;
}
// else proceed wiht the level order traversal
Q = enQueue(Q, root);
while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;
Q = deQueue(Q);
// Now we have a node of the tree in temp
// If its left is empty we insert the node else we enqueue its
if(temp -> left != NULL)
{
Q = enQueue(Q, temp -> left);
}
else
{
// Assign the new node to its left
temp -> left = newNode;
// Delete the queue and return
free(Q);
return root;
}
// Do the same for the right sub-tree of the traversed node
if(temp -> right != NULL)
{
Q = enQueue(Q, temp -> right);
}
else
{
// Assign the node to its right
temp -> right = newNode;
// Delete the queue and return
free(Q);
return root;
}
}
free(Q);
return root;
}
void levelOrder(struct binaryTreeNode * root)
{
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;
if(root == NULL)
return;
Q = enQueue(Q, root);
while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;
Q = deQueue(Q);
printf("%d ",temp -> data);
if(temp -> left)
Q = enQueue(Q, temp -> left);
if(temp -> right)
Q = enQueue(Q, temp -> right);
}
free(Q);
}
// Test the above functions
int main(void)
{
// Initialize the tree
struct binaryTreeNode * root = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
root-> data = 1;
struct binaryTreeNode * l = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
l -> data = 2;
struct binaryTreeNode * ll = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
ll -> data = 4;
ll -> left = ll -> right = NULL;
struct binaryTreeNode * lr = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
lr -> data = 5;
lr -> left = lr -> right = NULL;
l -> left = ll;
l -> right = lr;
struct binaryTreeNode * r = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
r -> data = 3;
r -> left = r -> right = NULL;
root -> left = l;
root -> right = r;
// print the tree
levelOrder(root);
printf("\n");
// Insert the element
root = insertInBinaryTree(root, 7);
// print again
levelOrder(root);
return 0;
}