# 3 Ways of Level Order Traversal of Binary Tree

18K
By Dhiraj 18 April, 2020

In the last article, we learned the basics of Tree data structure and performed different operations such as insert, search and traverse. For the tree traversal, we used recursive PreOrder, InOrder and PostOrder traversal but there are many other types of tree traversal too such as Level Order Traversal and Vertical Order Traversal. These travel techniques are mostly used for solving algorithms related to Tree data structure.

In this article, we will discuss Level Order Traversal of a binary tree. This technique can be used to find the left view and right view of the tree. There can be many ways for this traversal but in this article, we will learn 3 different ways of Level Order Traversal of a Binary tree.

## What is a Binary Tree

A tree is called a binary tree if each node has at max 2 children. It can have 0, 1 or 2 children. An empty tree is also a valid binary tree. Below are some properties of a binary tree that we discussed in our last article.

Let us assume that the height of the tree is h and the root node is at height zero.

• The number of nodes n in a full binary tree is 2^h+1 - 1.
• The number of nodes n in a complete binary tree is between 2^h and 2^h+1 - 1.
• The number of leaf nodes in a full binary tree is 2^h.
• The number of internal nodes in a full binary tree is 2^h - 1.
• The height of a tree of n nodes is log2(no of leaves).

All our discussion on a binary tree will be based on the binary tree below:

## Binary Tree Node

Let us implement our node class. In a binary tree, there can be at most 2 children and hence we have leftChild and rightChild node defined inside our Node class.

```public class BinaryTreeNode {

private int data;
private BinaryTreeNode leftNode;
private BinaryTreeNode rightNode;

}
```

Below is the template of our Binary Tree class.

```public class BinaryTree {

BinaryTreeNode root;

public BinaryTree(){
this.root = null;
}

public void levelOrderTraversal(BinaryTreeNode root){

}

public void levelOrderTraversalWithLevel(BinaryTreeNode root){

}

private Map<Integer, List<Integer>> addIntoLevelMap(Map<Integer, List<Integer>> map, int level, int data) {

}

public void levelOrderTraversalWithRecursion(BinaryTreeNode root){

}

private int findHeight(BinaryTreeNode root){

}

}
```

## Level Order Traversal Using Queue

This particular traversal technique is very similar to Breadth-First Search(BFS) technique that we discussed for the Graph data structure.

We simply start traversing the tree from the root of the tree and keep enqueuing the left and right child of a node to the queue. In order to visit all the nodes of a tree, we dequeue each node and print the node value.

This traversal technique prints all the visited nodes in a single line and hence this traversal technique can't be used extensively in solving algorithms. But with a little tweak in this travel technique, we can easily print level-wise tree nodes which we will look into the next section.

Below is the implementation of it in Java.

```public void levelOrderTraversal(BinaryTreeNode root){
List<Integer> data = new ArrayList<>();
while(!queue.isEmpty()){
BinaryTreeNode node = queue.poll();
if(node.getLeftNode() != null){
}
if(node.getRightNode() != null){
}
}
data.stream().forEach(nodeData -> System.out.print(nodeData + "  "));
System.out.println();
}
```
Output
`5  7  10  14  19  30  15  25  `

## Level Order Traversal Level Wise

This technique is very similar to above technique which uses a Queue but it prints the node value level wise and this is achieved by enqueing a null object in the queue after each level of node traversal is completed.

Now, the queustion is in which condition we enqueue null to the Queue. At first, we enqueue null just after enqueing the root node and from the next time whenever we encounter a null element in the queue, we again enqueue a null object in the queue and by the time we enqueue this null object, the queue has will have already enqueued with all the nodes of previous level.

Below is the algorithm for this technique.

```enqueue root
enqueue null
while queue is not empty
node = dequeue queue
if node is null
increase level
enqueue null again //meaning one level of nodes already enqueued
else
enqueue left and right child of node

```

The nullCount to 2 will be our exit condition assuming there all nodes of the tree are visited.

We have used map implementation to store level wise node data. Below is the implementation:

```public void levelOrderTraversalWithLevel(BinaryTreeNode root){
Map<Integer, List<Integer>> map = new HashMap<>();
int level = 0;
int nullCount = 1;
while(!queue.isEmpty()){
BinaryTreeNode node = queue.remove();
if(node == null){
++nullCount;
++level;
if(nullCount == 2){
break;
}
}else {
nullCount = 0 ;
if (node.getLeftNode() != null) {
}
if (node.getRightNode() != null) {
}
}
}
map.entrySet().stream().forEach(entry -> {
System.out.print(entry.getKey() + " : ");
entry.getValue().forEach(value -> System.out.print(value + " "));
System.out.println();
});
}

private Map<Integer, List<Integer>> addIntoLevelMap(Map<Integer, List<Integer>> map, int level, int data) {

if(map.get(level) == null){
map.put(level, new ArrayList<>());
}
return map;

}
```
Output
```0 : 5
1 : 7 10
2 : 14 19 30 15
3 : 25
```

## Level Order Traversal with Recursion

In this technique, we first find out the height of the tree and print each node as per the height of the tree.

```public void levelOrderTraversalWithRecursion(BinaryTreeNode root){
if(root == null){
return;
}
int leftLevel = findHeight(root.getLeftNode());
int rightLevel = findHeight(root.getRightNode());
int height = Math.max(leftLevel, rightLevel);
for (int i = 0; i <= height; i++){
System.out.print(i  + " :");
printLevel(root, i);
System.out.println();
}
}

private int findHeight(BinaryTreeNode root){
if(root == null){
return 0;
}
if(root.getRightNode() == null){
return findHeight(root.getLeftNode()) + 1;
}else{
return findHeight(root.getRightNode()) + 1;
}

}

private void printLevel(BinaryTreeNode root, int level){
if (root == null){
return;
}
if(level == 0){
System.out.print(root.getData() + " ");
}else if(level > 0){
printLevel(root.getLeftNode(), level - 1);
printLevel(root.getRightNode(), level - 1);
}
}

```

## Tree Runner

```public class BinaryTreeRunner {

public static void main(String[] args){
BinaryTree tree = new BinaryTree();
BinaryTreeNode root = new BinaryTreeNode(5);
tree.root = root;
root.setLeftNode(new BinaryTreeNode(7));
root.setRightNode(new BinaryTreeNode(10));
root.getLeftNode().setLeftNode(new BinaryTreeNode(14));
root.getLeftNode().setRightNode(new BinaryTreeNode(19));

root.getRightNode().setLeftNode(new BinaryTreeNode(30));
root.getRightNode().setRightNode(new BinaryTreeNode(15));

root.getRightNode().getRightNode().setLeftNode(new BinaryTreeNode(25));

tree.levelOrderTraversal(root);
System.out.println();

tree.levelOrderTraversalWithLevel(root);
System.out.println();

tree.levelOrderTraversalWithRecursion(root);
}

}
```

## Conclusion

In this article, we discussed 3 different techniques for Level Order Traversal of a binary tree and we will use these techniques in the next article to find out Left view and right view of the tree.

Share

### Tree Implementation Java

#### If You Appreciate This, You Can Consider:

We are thankful for your never ending support.

A technology savvy professional with an exceptional capacity to analyze, solve problems and multi-task. Technical expertise in highly scalable distributed systems, self-healing systems, and service-oriented architecture. Technical Skills: Java/J2EE, Spring, Hibernate, Reactive Programming, Microservices, Hystrix, Rest APIs, Java 8, Kafka, Kibana, Elasticsearch, etc.