Wednesday, December 2, 2015

Breadth First Traversal in Binary Trees

Hey guys, lets see the way of traversing the tree in a breadth first fashion.

So when the question comes for traversing the tree there are broadly two categories:

  1. Depth First Approach
    1. InOrder
    2. PreOrder
    3. PostOrder
  2. Breadth First Approach
In the first approach the style of traversing the tree is in a depth first fashion which means, that we keep on traversing the tree in a manner that goes vertically rather than horizontally.

In case of the breadth first approach we go layer by layer or in other words we go level by level. 

So if I have a tree like:
then in this tree, we will say that the :
  • 1 is at Level 0
  • 2,3 is at level 1
  • 4,5,6,7 is at level 2
  • 10,11,8,9 is at level 3
  • 12,13 is at level 4
So going forward with this approach we want to traverse the the tree in a level wise manner, and at the end the traversal would be : 1,2,3,4,5,6,7,10,11,8,9,12,13

Now coming to the code of this, it is very easy, if we uses queue in the code. We start by root and we keep pushing the children of the traversed node in to queue and keep on traversing the node taking from the queue.

Code here

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

class BFS {

 public static void main(String[] args) {
  Node n1 = new Node(1);
  Node n2 = new Node(2);
  Node n3 = new Node(3);
  Node n4 = new Node(4);
  Node n5 = new Node(5);
  Node n6 = new Node(6);
  Node n7 = new Node(7);
  Node n8 = new Node(8);
  Node n9 = new Node(9);
  Node n10 = new Node(10);
  Node n11 = new Node(11);
  Node n12 = new Node(12);
  Node n13 = new Node(13);
  
  n1.left = n2;
  n1.right = n3;
  
  n2.left = n4;
  n2.right = n5;
  
  n3.left = n6;
  n3.right = n7;
  
  n4.left = n4.right = null;
  
  n5.left = n10;
  n5.right = n11;
  
  n6.left = n6.right = null;
  
  n7.left = n8;
  n7.right = n9;
  
  n10.left = n12;
  n10.right = n13;
 
  n11.left = n11.right = null;
  
  n8.left = n8.right = null;
  n9.left = n9.right = null;
  
  Node root = n1; 
  Queue<Node> queue = new LinkedBlockingQueue<Node>();
  queue.add(root);
  
  while(!queue.isEmpty()){
   Node n = queue.poll();
   if(n.left !=null){
    queue.add(n.left);
   }
   if(n.right!=null){
    queue.add(n.right);
   }
   
   System.out.print(n.info + ", ");
  }
 }
 
}

 class Node{
 public Node left;
 public Node right;
 public int info;
 
 public Node(int info){
  this.info = info;
  this.left = null;
  this.left = null;
 }
 
 public String toString(){
  return "" + this.info;
 }
}

No comments:

Post a Comment