Level Order Traversal of Binary Tree

Problem: Level order traversal of binary tree.


Level Order Traversal


In level order traversal nodes of tree are traversed level-wise from left to right. Like depth first traversals ( Inorder,preorder and postorder traversal) level order traversal is not easily implemented recursively because each node stores address of its left and right children.

Queue data structure is used to store nodes level wise so that  each node’s children are visited. How we are going to use queue then?

We will first add root in queue. We will use a marker node and when marker node present at the start of queue, all nodes at that level are completed. As at level 0 only root presents, add marker node after that. Now until queue does not contain only marker node we will repeat following steps:

1. De-queue node present at the start of queue.

2.Add children of that node in queue if present.

3. If at the start of queue marker node present, that means we completed visiting all nodes at previous node. So de-queue marker node from start and again en-queue it. En-queue marker node again to make sure that all nodes at this level are completely accessed.

4. If queue only contains marker node that means all children are traversed that means all nodes are traversed.


Complexity: As all nodes of tree are visited in traversal, time complexity is O(n).