3 Oct 2013

BFS of a Binary Tree ( Level Order Traversal)

Problem Statement: 
    Traverse the Binary Tree Level by Level.

Solution :

There are two approches for BFS (Breadth First Search ) of a Binary Tree.
1. Using Queue
2. Recursive Approach.

In this post i will be solving the above problem with the recursive approach.

I have already posted the code for printing the nodes at a given level. So the only thing that we need to do for BFS of a tree is to calculate height of the tree and print nodes of the tree for each level.

Pls refer to the link for the working code.
Source Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**  
  * for printing BFS (recursive) 
  * @param root
  */
 public void printTreeBFS(Node root) {
  if(root==null)
   System.out.println("Empty Tree");
  
  int height=height(root);
  
  for(int i=1 ; i<=height ; i++){
   printLevel(root, i);
   System.out.println();
  }
 }
 
 /**
  * Prints nodes at a given level
  * @param root
  * @param level
  */
 public void printLevel(Node root, int level) {
   if(root==null)
    return ;
   
   if(level==1)
    System.out.print(root.data + "\t");
 
   printLevel(root.left, level-1) ;
   printLevel(root.right, level-1) ;
 }

No comments:

Post a Comment