Blog

Problem statement:
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.
ORa
Given a binary tree, print its nodes level by level. i.e. all nodes present at level 1 should be printed first followed by nodes of level 2 and so on.. All nodes for any level should be printed from left to right.

Level order traversal is also called breadth first traversal for the tree.

Steps for Level order traversal algorithm:

1. Create an empty queue and push root node into it.
2. Repeat following steps 3, 4 and 5 until queue is not empty
3. Pop a node from queue and process it
4. If left child node is not null then push it to queue.
5. If right child node is not null then push it to queue.

Following is the Java implementation for above steps

	void levelOrderTopToBottomTraversal(Node root) {
		Queue<Node> queue = new LinkedList>();
		queue.add(root);
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			processNode(node);
			/* Enqueue left child */
			if (node.getLeftChild() != null)
				queue.add(node.getLeftChild());
			/* Enqueue right child */
			if (node.getRightChild() != null)
				queue.add(node.getRightChild());
		}
	}
	private void processNode(Node root) {
		System.out.print(root.getData() + " ");
	}

Here is the full Java program for reference:

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

public class TreeLevelOrderTraversals {
	public Node createTree() {
		Node root = new Node(12);
		root.setLeftChild(new Node(23));
		root.setRightChild(new Node(18));
		root.getLeftChild().setLeftChild(new Node(11));
		root.getLeftChild().setRightChild(new Node(43));
		root.getRightChild().setLeftChild(new Node(19));
		root.getRightChild().setRightChild(new Node(50));
		return root;
	}
	void levelOrderTopToBottomTraversal(Node root) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			processNode(node);
			/* Enqueue left child */
			if (node.getLeftChild() != null) {
				queue.add(node.getLeftChild());
			}
			/* Enqueue right child */
			if (node.getRightChild() != null) {
				queue.add(node.getRightChild());
			}
		}
	}
	private void processNode(Node root) {
		System.out.print(root.getData() + " ");
	}
	
	public static void main(String[] args) {
		TreeLevelOrderTraversals bt = new TreeLevelOrderTraversals();
		Node root = bt.createTree();
		System.out.println("Print Tree nodes in level order \t");
		bt.levelOrderTopToBottomTraversal(root);
	}
	class Node {
		private int data;
		private Node leftChild;
		private Node rightChild;
		public Node(int data) {
			this.data = data;
			leftChild = null;
			rightChild = null;
		}
		public int getData() {
			return data;
		}
		public void setData(int data) {
			this.data = data;
		}
		public Node getLeftChild() {
			return leftChild;
		}
		public void setLeftChild(Node leftChild) {
			this.leftChild = leftChild;
		}
		public Node getRightChild() {
			return rightChild;
		}
		public void setRightChild(Node rightChild) {
			this.rightChild = rightChild;
		}
	}
}

Output of above Java code is

Print Tree nodes in level order 	
12 23 18 11 43 19 50