Skip to main content

Level order traversal using queue in c

C program for Level order traversal using queue. Here more information.

// Include header file
#include <stdio.h>
#include <stdlib.h>
/*
  C program for
  Level order tree traversal using queue
*/
// Binary Tree Node
typedef struct TreeNode
{
	// Define useful field of TreeNode
	int data;
	struct TreeNode * left;
	struct TreeNode * right;
}TreeNode;

// Create Q node
typedef struct QNode
{
	// Define useful field of QNode
	struct TreeNode * data;
	struct QNode * next;
}QNode;

QNode * getQNode(TreeNode * node)
{
	// Create dynamic memory of QNode
	QNode * ref = (QNode * ) malloc(sizeof(QNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->data = node;
	ref->next = NULL;
	return ref;
}


TreeNode * getTreeNode(int data)
{
	// Create dynamic memory of TreeNode
	TreeNode * ref = (TreeNode * ) malloc(sizeof(TreeNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set node value
	ref->data = data;
	ref->left = NULL;
	ref->right = NULL;
	return ref;
}
typedef struct MyQueue
{
	// Define useful field of MyQueue
	struct QNode * head;
	struct QNode * tail;
	int count;
}MyQueue;

MyQueue * getMyQueue()
{
	// Create dynamic memory of MyQueue
	MyQueue * ref = (MyQueue * ) malloc(sizeof(MyQueue));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->head = NULL;
	ref->tail = NULL;
	ref->count = 0;
	return ref;
}
int size(MyQueue * ref)
{
	return ref->count;
}
int isEmpty(MyQueue * ref)
{
	return ref->count == 0;
}
// Add new node of queue
void enqueue(MyQueue * ref, TreeNode * value)
{
	// Create a new node
	QNode * node = getQNode(value);
	if ((ref->head == NULL))
	{
		// Add first element into queue
		ref->head = node;
	}
	else
	{
		// Add node at the end using tail
		ref->tail->next = node;
	}
	ref->count++;
	ref->tail = node;
}
// Delete a element into queue
void dequeue(MyQueue * ref)
{
	if ((ref->head == NULL))
	{
		// Empty Queue
		return;
	}
  	QNode *t = ref->head;
	// Visit next node
	ref->head = ref->head->next;
	ref->count--;
	if ((ref->head == NULL))
	{
		// When deleting a last node of linked list
		ref->tail = NULL;
	}
  	free(t);
}
// Get front node
TreeNode * peek(MyQueue * ref)
{
	if ((ref->head == NULL))
	{
		return NULL;
	}
	return ref->head->data;
}
typedef struct BinaryTree
{
	// Define useful field of BinaryTree
	struct TreeNode * root;
}BinaryTree;

BinaryTree * getBinaryTree()
{
	// Create dynamic memory of BinaryTree
	BinaryTree * ref = (BinaryTree * ) malloc(sizeof(BinaryTree));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set initial tree root
	ref->root = NULL;
	return ref;
}
void levelOrder(BinaryTree * ref)
{
	if ((ref->root != NULL))
	{
		MyQueue * q = getMyQueue();
		// Add first node
		enqueue(q, ref->root);
		TreeNode * node = ref->root;
		while (isEmpty(q) == 0 && node != NULL)
		{
			if ((node->left != NULL))
			{
				// Add left child node
				enqueue(q, node->left);
			}
			if ((node->right != NULL))
			{
				// Add right child node
				enqueue(q, node->right);
			}
			// Display level node
			printf(" %d ", node->data);
			// Remove current node
			dequeue(q);
			// Get new head
			node = peek(q);
		}
	}
	else
	{
		printf("Empty Tree");
	}
}
int main()
{
	// Create new tree
	BinaryTree * tree = getBinaryTree();
	/*
	  Make A Binary Tree
	  -----------------------
	         1
	       /   \
	      2     3
	     /     / \
	    4     5   6
	   /     / \
	  7     8   9
	*/
	// Adding tree nodes
	tree->root = getTreeNode(1);
	tree->root->left = getTreeNode(2);
	tree->root->right = getTreeNode(3);
	tree->root->right->right = getTreeNode(6);
	tree->root->right->left = getTreeNode(5);
	tree->root->left->left = getTreeNode(4);
	tree->root->left->left->left = getTreeNode(7);
	tree->root->right->left->left = getTreeNode(8);
	tree->root->right->left->right = getTreeNode(9);
	// Display level order element
	levelOrder(tree);
}

Output

 1  2  3  4  5  6  7  8  9




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment