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
Table of Contents
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
[vc_row][vc_column width=”2/3″][td_block_text_with_title custom_title=”Java Code”][/td_block_text_with_title][/vc_column][/vc_row]
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 ItDry 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.
[vc_row][vc_column width=”2/3″][td_block_text_with_title custom_title=”Conclusion”][/td_block_text_with_title][/vc_column][/vc_row] Above java code to print the Level order traversal of a binary tree in Java. This will print all the nodes of the above binary tree in linear time. Time complexity of the above code will be O(n). Because we are using a queue to the Space complexity will be O(n) where n is the number of nodes of the binary tree.
[vc_row][vc_column width=”2/3″][td_block_text_with_title custom_title=”References”][/td_block_text_with_title][/vc_column][/vc_row]