*793*

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.

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.