How to implement Level Order Traversal in Binary Tree?

Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This search is referred to as a breadth-first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.

Java implementation of level order traversal is as below:

package askgif.tree;

import java.util.LinkedList;
import java.util.Queue;

class Node
{
 int data;
 Node left, right;
 
 public Node(int item)
 {
 data = item;
 left = right = null;
 }
}

class BinaryTree
{
 Node root;
 
 BinaryTree()
 {
 root = null;
 }
 
}

public class TreeQuestions {

	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		Node root = new Node(1);
		binaryTree.root = root;
		binaryTree.root.left = new Node(2);
		binaryTree.root.right = new Node(3);
		binaryTree.root.left.left = new Node(4);
		binaryTree.root.left.right = new Node(5);
 
 PrintLevelOrderTraversal(root);

	}

	private static void PrintLevelOrderTraversal(Node treeNode) {
		if(treeNode == null)
			return;
		
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(treeNode);
		while(!queue.isEmpty()) {
			Node temp = queue.remove();
			System.out.println(temp.data);
			if(temp.left != null)
				queue.add(temp.left);
			if(temp.right != null)
				queue.add(temp.right);
		}
		
	}

}

output:

1
2
3
4
5

Time Complexity: O(n). as we are processing each node of the tree at once.