fork(5) download
copy 
#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;
}
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 
1 2 3 4 5 7
https://ideone.com/CFeFKF
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!