Level Order Traversal of a Binary Tree

ALSO CHECK: Algorithms and System Design Interview Questions

Let's say we have below Binary Tree

We need to print 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.

There are two ways by which we can print the Level Order Traversal of any tree:
1). Print in one line:For the above tree it would be:
a b c d e f g h i j k l.

2). Print in level by level:For the above tree it would be:
a
b c
d e f g
h i j k l

ALSO CHECK: Vertical Order Traversal of a Binary Tree

Algorithm For Printing In One Line
1). We need to use Queue to do this.
2). We will start from root, we will enqueue the root node.
3). Now we will started iterating the queue in a while loop till its not empty.
4). During each iteration, we will dequeue the queue, print the value and then we need to enqueue the left and the right child of current node.

ALSO CHECK: Binary Search Trees, Balance Search Trees, 2-3 ST, Red- Black BST

Algorithm For Print Level By Level
1). We need to use Queue to do this.
2). We will start from root, we will enqueue the root node. Then we will enqueue NULL. Whenever a level is over we will enqueue NULL, this will help us in identifying the level.
3). Now we will started iterating the queue in a while loop till its not empty.
4). During each iteration, we will dequeue the queue, print the value and then we need to enqueue the left and the right child of current node. Whenever we encounter null, we need to change the level (e.g print \n) and then enqueue NULL.
5). Whenever we get two NULL's consecutively, that means we have completed the traversal.

	void levelOrder(Node root){
	if (root == null)
	return;
	Queue<Node> q = new LinkedList<>();
	// Pushing root node into the queue.
	q.add(root);
	// Pushing delimiter into the queue.
	q.add(null);
	// Executing loop till queue becomes
	// empty
	while (!q.isEmpty()) {
	Node curr = q.poll();
	// condition to check the
	// occurence of next level
	if (curr == null) {
	if (!q.isEmpty()) {
	q.add(null);
	System.out.println();
	}
	} else {
	// Pushing left child current node
	if (curr.left != null)
	q.add(curr.left);
	// Pushing right child current node
	if (curr.right != null)
	q.add(curr.right);
	System.out.print(curr.data + " ");
	}
	}
	}

view raw BinaryTreeLevelOrder.java hosted with ❤ by GitHub

-K Himaanshu Shuklaa..