Line by line level order traversal of a binary tree and its related problems

In this article , let us discuss how we can write code for line by line level order traversal. For the above figure, line by line level order traversal would be:
1//1st level
2 3//2nd level
5 6//3rd level

Java Code:

public static void printLevel(Node root){
if(root==null)return;
Queue<Node> q=new LinkedList<>();
q.add(root);
while(q.isEmpty()==false){
int count=q.size();
for(int i=0;i<count;i++){
Node curr=q.poll();
System.out.print(curr.key+” “);
if(curr.left!=null)
q.add(curr.left);
if(curr.right!=null)
q.add(curr.right);
}
System.out.println();
}
}

Approach:

We use two loops, one while loop(outer loop) and one for loop(inner loop). Outer loop is used to stop the processing after each element is printed.Inner loop is used to print each level of tree. We use queue here to store the levels of tree and use queue’s size to restrict the inner loop such that it prints only current level as the queue can contain both current level and next level at a point of time.

Dry run using above diagram as example:
1. We first check for if the tree is empty or not, if the tree is empty we won’t do any thing but here as per the above figure tree is non empty.
2.If the tree is non empty, we then enqueue the first node into the queue, queue contains node “1” now.

3. We then start a loop while queue is not empty. As the queue contains node “1”, we enter into the while loop.

4. We then calculate the size of the queue , the size is 1 now as it contains only node “1” . This is needed to iterate size number of times.
5. We then print “1” after dequeueing it and then enqueue node “1” left and right children(nodes “2” and “3”) to the queue.
6. As the inner loop is over, we print a new line.
7.We again, compute the size of the queue, now the size is two as the queue contains nodes “2” and “3”.
8. We iterate the for loop for two(size) times and print node “2” by dequeueing it , after dequeueing node “2” , we enqueue node “2” left and right children to the queue(node “5” and “6”).

9. We then print node “3” by dequeuing it from the queue and add no nodes to the queue because node “3 ” does not have any children. We exit the inner loop as it the loop is for only 2 (size) times.

10. As inner loop is over, we print a new line. After new line is printed, we again compute the size of queue, it is two now as it contains nodes “5” and “6”.

11. Inner loop is executed 2(size) times and nodes “5” and “6” are printed after they are dequeued. As nodes “5” and “6” don’t have any children, we don’t not enqueue any node to the queue making queue empty.

12. Queue being empty means , the processing is complete i.e. outer while loop won’t be executed further

Problems that can be solved by extending above approach:

Left view of tree:

We can solve this problem by printing only first element of each level(using the queue’s size logic discussed above).

https://practice.geeksforgeeks.org/problems/left-view-of-binary-tree/1

Right view of tree:
We can solve this problem by printing only last element of each level

https://practice.geeksforgeeks.org/problems/right-view-of-binary-tree/1

Maximum Width of Tree:
We can solve this problem by taking a variable for width , initializing it with 0 and we compare queue’s size for each level and update the width variable every time if the queue’s size is greater than current width variable value.

https://practice.geeksforgeeks.org/problems/maximum-width-of-tree/1