Table of Contents

Level order traversal or breadth first traversal is traversing the same level nodes of a tree then move to next level. We can use queue to print the level order traversal of a binary tree.

Write a Java program to print the level order traversal of a binary tree.

Sometimes people say level order traversal as breadth first search (BFS) where they meant the same level order traversal of a tree.

For above tree the level order traversal or breadth first traversal will give below output

**Output:** 1 2 3 4 5 6 7

Binary Tree Level Order Traversal

## Algorithm for Level Order Traversal of Tree

**Step1:** Add the Root Node in a Queue**Step2:** Loop through the Queue till its not empty**Step3:** Dequeue the Node from the Queue, name it temp**Step4:** Print temp’s Data**Step5:** If temp has Left Child then Add left child in Queue**Step6:** If temp has Right Child then Add right child in Queue**Step7:** Goto Step 2

## Demonstration of Algorithm

Here is binary tree level order traversal steps shown using diagram. Go through every step and understand it. I bet you will remember this forever.

Below is the Tree with root = Node 1. And we have an empty queue

We will add root element in the queue. So Node 1 will be moved to the queue.

Now we will dequeue the element and temp will be pointing to Node 1 and Node 2 and Node 3 are left and right child of Node 1. We will Print temp.data to Print 1

Left and Right child of Node 1 will be added in the queue. So Node 2 and Node 3 will be inserted in the queue.

Now we will dequeue and temp will be pointed to Node 2. Print Node 2.

Now Node 2 has Node 4 and Node 5 as left and right child so we will add them in the queue.

Now we will dequeue Node 3 and Print 3. Noe temp is pointing to Node 3 and its left and right child are Node 6 and Node 7.

We will add Node 6 and Node 7 in the Queue.

Now we will dequeue Node 4 and Print it. As there are no children for Node 4 so nothing will be added in the queue.

Now we will dequeue Node 5 and Print it. As there are no children for Node 5 so nothing will be added in the queue.

Now we will dequeue Node 6 and Print it. As there are no children for Node 6 so nothing will be added in the queue.

Now we will dequeue Node 7 and Print it. As there are no children for Node 7 so nothing will be added in the queue.

Now as the queue is empty so control will come out of the while loop. And we will see that our java code has printed the binary tree level order traversal.

## Java Code for Level Order Traversal

#### Java Code

```
import java.util.LinkedList;
import java.util.Queue;
class Node {
String data;
Node left;
Node right;
Node rightNext;
public Node(String data)
{
this.data = data;
this.left = null;
this.right = null;
this.rightNext = null;
}
}
class BinaryTree {
public Node CreateTree()
{
Node n1 = new Node("1");
Node n2 = new Node("2");
Node n3 = new Node("3");
Node n4 = new Node("4");
Node n5 = new Node("5");
Node n6 = new Node("6");
Node n7 = new Node("7");
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
return n1;
}
public void PrintLevelOrder(Node root)
{
System.out.print("Print Level Order ");
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty())
{
Node temp = queue.remove();
System.out.print(temp.data + " ");
if(temp.left!=null)
queue.add(temp.left);
if(temp.right!=null)
queue.add(temp.right);
}
System.out.println();
}
}
public class test {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
Node root = bt.CreateTree();
bt.PrintLevelOrder(root);
}
}
```

Try It### Dry Run for above java program

Steps involved to print level order traversal of a binary tree

- If root is not null then add the root in the queue.
- Node 1 will be added in the Queue.
- Queue is not empty so remove the node from the queue.
- We will have Node 1 with us. Print Node 1.
- If Node 1 has left and right child then add them in the queue.
- Node 2 and 3 will get added in the Queue.
- Now Queue is not empty so remove the node from the queue
- We will get Node 2 with us. Print Node 2.
- If Node 2 has left and right child then add them in the queue.
- Node 4 and 5 will be added in the Queue.
- Queue contains currently Node 3, Node 4 and Node 5
- Queue is not empty so remove the node from the queue
- We will get Node 3 with us. Print Node 3.
- If Node 3 has left and right child then add them in the queue.
- Node 6 and 7 will get added in the queue.
- Queue contains currently Node 4, Node 5, Node 6, Node 7
- Queue is not empty so remove the node from the queue.
- We will get Node 4. Print Node 4.
- If Node 4 has left and right child then add them in the queue.
- Nothing will be added in the queue because Node 4 has no children.
- Queue is not empty so remove the node from the queue.
- We will get Node 5. Print Node 5.
- If Node 5 has left and right child then add them in the queue.
- Nothing will be added in the queue because Node 5 has no children.
- Queue is not empty so remove the node from the queue.
- We will get Node 6. Print Node 6.
- If Node 6 has left and right child then add them in the queue.
- Nothing will be added in the queue because Node 6 has not children.
- Queue is not empty so remove the node from the queue.
- We will get Node 7. Print Node 7.
- If Node 7 has left and right child then add them in the queue.
- Nothing will be added in the queue because Node 7 has no children.
- Queue is empty so break the loop.