Pre-order, In-order and Post-order traversal of tree use Depth First Search (DFS). These are called DFS since these techniques visit the tree deeper and deeper until it reaches the leaf node. Level-order traversal (as the name suggest) visits the nodes level by level. Level Order Traversal is Breadth First Search(BFS). Below diagram shows Level Order traversal of a binary tree.
Let's see implementation techniques:
Without Using External Storage
Applying recursion in BFS traversal is non-trivial. So in this case, the most obvious approach could be to print the nodes at each level iteratively. Above tree has three level, which equals the height of the tree. Now, how do we print all nodes at a given level?
To print nodes at level 2(i.e. 2 and 3), we need to start at the root and keep traversing down the tree recursively. Each time we go one level down the level value needs to be reduced by 1. This way both left and right subtree will keep going down the tree independently until the level becomes 1.
public void levelOrderIteratively(){
int height = this.getHeight(root);
for(int i=1; i<= height; i++){
printNodesAtGivenLevel(root, i);
}
}
//other methods are given in full implementation
The below implementation prints all nodes in the same line. In above method, we are calling a separate method to print for each level so we can format it the way we want (something like below can be easily done by tweaking above for loop.
Nodes at level 1 = 1
Nodes at level 2 = 2 3
Nodes at level 3 = 4 5 6
The below implementation prints all nodes in the same line. In above method, we are calling a separate method to print for each level so we can format it the way we want (something like below can be easily done by tweaking above for loop.
Nodes at level 1 = 1
Nodes at level 2 = 2 3
Nodes at level 3 = 4 5 6
Using external storage / Using Queue
One of the de-facto approaches to implementing any breadth-first traversal is using Queue (First in First out data structure). BFS enables to visit nodes of the tree level by level.
Java Implementation
Below java implementation provides level order traversal using an iterative technique which doesn't require extra storage as well as using Queue.
package algo;
import java.util.LinkedList;
import java.util.Queue;
/**
* Generic Binary Tree Implementation
* @author Siddheshwar
*
* @param <E>
*/
public class BinaryTree<E> {
/**
* Root node of the tree
*/
Node<E> root;
/**
* Node class to represent each node of the tree
*/
static class Node<E> {
E data;
Node<E> left;
Node<E> right;
Node(E d) {
this.data = d;
this.left = null;
this.right = null;
}
}
/**
* Get height of the tree
*
* @param node
* root node
* @return height of the tree which is max of left subtree height or right
* subtree height + 1 (for root)
*/
public int getHeight(Node<E> node) {
if (node == null) {
return 0;
}
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
/**
* Print binary tree in level-order
*/
public void levelOrderIteratively() {
int height = this.getHeight(root);
for (int i = 1; i <= height; i++) {
printNodesAtGivenLevel(root, i);
}
}
/**
* Print nodes at the given level
*
* @param node
* first call with root node
* @param level
* first call with the level for which we need to print
*/
private void printNodesAtGivenLevel(Node<E> node, int level) {
if (node == null)
return;
if (level == 1) {
System.out.print(node.data + " ");
return;
}
printNodesAtGivenLevel(node.left, level - 1);
printNodesAtGivenLevel(node.right, level - 1);
}
/**
* Prints level order traversal using Queue
*/
public void levelOrderQueue() {
if (root == null) {
return;
}
Queue<Node<E>> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.print(node.data + " ");
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
/**
* Method to test the tree construction
*/
public static void main(String[] args) {
BinaryTree<Integer> bt = new BinaryTree<Integer>();
bt.root = new Node<>(1);
bt.root.left = new Node<>(2);
bt.root.right = new Node<>(3);
bt.root.left.left = new Node<>(4);
bt.root.right.left = new Node<>(5);
bt.root.right.right = new Node<>(6);
System.out.println(" height =" + bt.getHeight(bt.root));
bt.levelOrderIteratively();
System.out.println();
bt.levelOrderQueue();
}
}
--
keep coding !!!
keep coding !!!
