Level Order Traversal- Algo 14

 Using Queue Data structure

Approach 1 – For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.

Pseudo Code :

printLevelorder(tree)

1) Create an empty queue q

2) temp_node = root /*start from root*/

3) Loop while temp_node is not NULL

    a) print temp_node->data.

    b) Enqueue temp_node’s children (first left then right children) to q

    c) Dequeue a node from q and assign it’s value to temp_node

import java.util.LinkedList;

import java.util.Queue;

public class LevelOrderTraversal {

     public static void main(String[] args) {

          BinarySearch bs = new BinarySearch();

          bs.insertNode(20);

          bs.insertNode(10);

          bs.insertNode(25);

          bs.insertNode(5);

          bs.insertNode(15);

          bs.insertNode(23);

          bs.insertNode(8);

          bs.insertNode(12);

          LevelOrderTraversal lot= new LevelOrderTraversal();

          lot.levelOrderTraversal(bs.root);

     }

     public void levelOrderTraversal(Node node){

          Node currentNode=null;

          if(node == null)

              return;

          Queue<Node> queue= new LinkedList<Node>();

          queue.add(node);

          while(!queue.isEmpty()){

              currentNode= queue.poll();

              System.out.println(currentNode.data);

              if(currentNode.leftChild!=null)

                   queue.add(currentNode.leftChild);

              if(currentNode.rightChild!=null)

                   queue.add(currentNode.rightChild);

          }

     }

}

Output:

20        10        25        5          15        23        8          12