Home Theory Level order Traversal in a Binary Tree

Level order Traversal in a Binary Tree

by nikoo28
0 comment

We discussed the basic tree traversals in this post –

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.
binary_tree_2
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:-
level_order_1
level_order_2
level_order_3
level_order_4

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.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More