Levelorder Traversal in Binary Tree

In Levelorder traversal,we have to follow the level of the tree,means first we have to traverse the level-0,then level-1 and so on.

Process is defined as follows :

• process level-0
• process the level-1 till last level

Working Process of Postorde Traversal

Code Implementation of Levelorder Traversal

• Debug code with the below Binary tree :

#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
struct BinaryTreeNode                  // Node Structure Initialization
{
	char  data;                         // for data element
	struct BinaryTreeNode* left;   // for storing the address of left child
	struct BinaryTreeNode* right;  // for storing the address of right child
};
// LevelOrder Traversing method.
void LevelOrderTraversing(struct BinaryTreeNode* rootNode)
{
	std::queue<struct BinaryTreeNode*> QueueForNode;
	struct BinaryTreeNode* TempNode;
	if (rootNode)
	{
		QueueForNode.push(rootNode);
		while (!QueueForNode.empty())
		{
			TempNode = QueueForNode.front();
			QueueForNode.pop();
			std::cout << TempNode->data << " ";
			if(TempNode->left)
				QueueForNode.push(TempNode->left);
			if(TempNode->right)
				QueueForNode.push(TempNode->right);
		}
	}
}
int main()
{
	//initialize 5 node to create the binary tree.
	struct BinaryTreeNode* A = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* B = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* C = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* D = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* E = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	//address arrangement.
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	//leaf node has zero child.
	C->left = NULL;
	C->right = NULL;
	D->left = NULL;
	D->right = NULL;
	E->left = NULL;
	E->right = NULL;
	//Data Initilization.
	A->data = 'A';
	B->data = 'B';
	C->data = 'C';
	D->data = 'D';
	E->data = 'E';
	// call the function to print the LevelOrder Sequence
	printf("LevelOrder Traversal will be : ");
	LevelOrderTraversing(A);
	_getch();
	return 0;
}

 Time & Space Complexity of Levelorder Traversal

• Time Complexity will be O(n).
• Space Complexity will be O(n).