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<>(); Queue<BinaryTreeNode> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ BinaryTreeNode node = queue.poll(); data.add(node.getData()); if(node.getLeftNode() != null){ queue.add(node.getLeftNode()); } if(node.getRightNode() != null){ queue.add(node.getRightNode()); } } 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<>(); Queue<BinaryTreeNode> queue = new LinkedList<>(); queue.add(root); int level = 0; queue.add(null); int nullCount = 1; while(!queue.isEmpty()){ BinaryTreeNode node = queue.remove(); if(node == null){ ++nullCount; ++level; if(nullCount == 2){ break; } queue.add(null); }else { addIntoLevelMap(map, level, node.getData()); nullCount = 0 ; if (node.getLeftNode() != null) { queue.add(node.getLeftNode()); } if (node.getRightNode() != null) { queue.add(node.getRightNode()); } } } 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<>()); } map.get(level).add(data); 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.
