Definition: In the Level Order Traversal, the binary tree is traversed level-wise starting from the first to last level sequentially.

Consider the following binary tree image:

The Level Order Traversal of the above Binary Tree will be: 10 4 8 50 24 5 12 18.

Algorithm:

The Level Order Traversal can be implemented efficiently using a Queue.
1.Create an empty queue q.
2.Push the root node of tree to q. That is, q.push(root).
3.Loop while the queue is not empty:
4.Pop the top node from queue and print the node.
5.Enqueue node's children (first left then right children) to q
6.Repeat the process until queue is not empty.

Problem:

You are given a pointer to the root of a binary tree. You need to print the level order traversal of this tree. In level order traversal, we visit the nodes level by level from left to right. You only have to complete the function. For example:

1
\
2
\
5
/ \
3 6
\
4

For the above tree, the level order traversal is 1 -> 2 -> 5 -> 3 -> 6 -> 4.

Input Format

You are given a function,

void levelOrder(Node root) {
}

Constraints

1 <= Nodes in the tree <= 500

Output Format

Print the values in a single line separated by a space.

Sample Input

1
\
2
\
5
/ \
3 6
\
4

Sample Output

1 2 5 3 6 4

Explanation

We need to print the nodes level by level. We process each level from left to right. Level Order Traversal: 1 -> 2 -> 5 -> 3 -> 6 -> 4.

Code:

package tree;
import java.util.LinkedList;
import java.util.Queue;
public class LevelOrderTraversal {
public static void level(Node root) {
if(root == null)
return;
Queue<Node> qu = new LinkedList<>();
qu.add(root);
while(!qu.isEmpty()) {
Node temp = qu.remove();
System.out.print(temp.data + " ");
if(temp.left != null)
qu.add(temp.left);
if(temp.right != null)
qu.add(temp.right);
}
}
public static void main(String[] args) {
Node root= new Node(10);
root.left= new Node(4);
root.right= new Node(8);
root.left.left= new Node(50);
root.left.right= new Node(24);
root.left.left.right = new Node(18);
root.right.left = new Node(5);
root.right.right = new Node(12);
level(root);
}
}

Output:
10 4 8 50 24 5 12 18

Time Complexity:O(N), where N is the number of nodes in the Tree. Auxiliary Space:O(N).

Hope you all get the concept of level order traversal using queue.

In the next blog we will see other tree implementation using both methods i.e iterative and recursive in java.

## Leave a Reply