Level Order Binary Tree Traversal(BFS)

Please read Tree Introduction before proceeding.

I have already explained how to do following Tree Traversal in java.

1. Pre-Order
2. Post Order
3. In Order.

Today, Lets discuss how to do level order(BFS) Tree Traversing

In the above Example, There are 4 levels. At level 1, there is one node(root). At level 2, we have 2 nodes, node 2 and 3. At level 3, we have 4 nodes,  node 5,6,4 and 7,  and At level4, we have 3 nodes, node 9,8 and 10.
If we do level order traversing for above tree then output would be: 1,2,3,5,6,4,7,9,8,10.

                                                      Before moving to solution, we have to understand what data structure should be used here to store the intermediate nodes. To do level order traversing, we have use data structure through which we can retrieve the node in Inserting order or First In First Out(FIFO). Queue works on "First In First Out" Principle. Instead of using stack we have to use queue to do level order traversing.
          
Code Implementation(Iterative Approach)method:

public void levelOrderTraversing(BinaryTree root){
      if(root==null)return;
      LinkedList<BinaryDataTree> queue = new LinkedList<BinaryDataTree>();
      queue.addFirst(root);
      while (!queue.isEmpty()) {
            BinaryDataTree temp = queue.pollLast();
            if (temp.getLeft() != null) {
                    queue.addFirst(temp.getLeft());
             }
            if (temp.getRight() != null) {
                    queue.addFirst(temp.getRight());
             }
            System.out.print(temp.getData() + "   ");
      }      
}




Level Order Traversing(Recursive Approach):

As we all know, If we solve any problem using recursion, it maintains a stack to keep track of method, is called method stack. For level order traversing we need a Data structure which works on the "FIFO".
                  Now Question is, how can we solve this problem using recursion? If we know the height of the tree, Height of tree is nothing but number of levels in tree. We can pass the level along with the child element and keep calling method until we get the all the nodes of a level, and then print them all.


Code Implementation():

void levelOrderPrintingRecusriveWay(BinaryDataTree root) {
        if (root == null)
            return;
        int height = heightOfTreeByRecursiveWay(root);
        for(int i=1; i<=height; i++)
            levelOrderPrintingRecusriveWay(root, i);
    }

    void levelOrderPrintingRecusriveWay(BinaryDataTree root, int level) {
        if(root==null)return;
        if (level == 1) {
            System.out.print(root.getData() + " ");
            return;

        }
        levelOrderPrintingRecusriveWay(root.getLeft(), level - 1);
        levelOrderPrintingRecusriveWay(root.getRight(), level - 1);
    }

public int heightOfTreeByRecursiveWay(BinaryDataTree root) {
        if (root == null)
            return 0;
        int l = heightOfTreeByRecursiveWay(root.getLeft());
        int r = heightOfTreeByRecursiveWay(root.getRight());
        if (l > r)
            return l + 1;
        return r + 1;
    }