Level order Traversal in a Binary Tree

We discussed the basic tree traversals in this post –

• Basic tree traversals

We learned about the pre-order traversal, in-order traversal and post-order traversal. These are standard traversals that are related with root, left sub-tree and the right sub-tree. Level order traversal follows an entirely different approach and is not related with the left sub-tree and the right sub-tree. It does not hold the same property for all the nodes and hence recursive technique cannot be applied to level order traversal.

Let us try to understand with the help of our sample tree.

In this example, we have 3 levels. So the according to level order traversal –

• Root – 1
• Level 1 – 2, 3
• Level 2 – 4, 5, 6, 7
  

Finally, we now have the level order traversal as:- 1, 2, 3, 4, 5, 6, 7. The algorithm that we will use is by taking the help of a queue.

• Visit the root
• While traversing level 1, keep all the elements at level l+1 in queue.
• Go to the next level and visit all the nodes at that level
• Repeat this process until all levels are completed.

This can be represented as:-

void levelOrder(struct binaryTreeNode * root)
{
	// Create a temporary binary tree node
	struct binaryTreeNode * temp = NULL;
	
	// Create a queue
	struct queue * Q = NULL;
	
	// If the tree is empty we simply need to return
	if(root == NULL)
		return;
		
	// If the tree is not empty
	// We add the root node to the queue
	Q = enQueue(Q, root);
	
	// We need to loop until our queue is not empty
	while(!isQueueEmpty(Q))
	{
		// Store the front element of queue in temporary variable
		temp = Q -> front -> data;
		
		// Dequeue
		Q = deQueue(Q);

		// Process the current node
		printf("%d ",temp -> data);
		
		// If the left child exists
		if(temp -> left)
			Q = enQueue(Q, temp -> left);
		
		// If the right child exists, enqueue that also
		if(temp -> right)
			Q = enQueue(Q, temp -> right);
	}
	
	// Delete the queue
	free(Q);
}

Time Complexity:- O(n)
Space Complexity:- O(n), Since in the worst case, all the nodes on the entire last level could be in the queue simultaneously.

You can download the complete working code from here. Use your favorite editor to open.