Binary Tree Traversal Using Breadth First Search Java Program

In this post we’ll see a Java program to do a Binary tree traversal using breadth first search which is also known as level order traversal of binary tree.

Breadth first search

Contrary to the depth first search where traversal is done by moving to node in the next level, in breadth first search all the nodes with in the same level are visited then only next level is visited.

For depth search Java program refer this post- Binary Tree Traversal Using Depth First Search Java Program

The level order traversal of the binary tree in the above image will happen in the following order-

Level 0 – 50
Level 1- 30, 70
Level 2- 15, 35, 62, 87
Level 3- 7, 22, 31

Binary Tree- Breadth first search Java program

Breadth first Java program for a binary tree can be written using both-

recursive method
non-recursive method

Breadth first search Recursive Java program

To write a Java program to recursively do a level order traversal of a binary tree you need to calculate height of the tree and then call method for level order traversal for level 0 to max level of the binary tree.

public void levelOrder(){
  int height = calculateTreeHeight(root);
  for(int i = 0; i < height; i++){
    levelOrderTraversal(root, i);
  }
}

// Method for breadth first search
public void levelOrderTraversal(Node node, int level){
  if(node == null){
    return;
  }
  if(level == 0){
    System.out.print(node.value + " ");
  }else{
    levelOrderTraversal(node.left, level-1);
    levelOrderTraversal(node.right, level-1);
  }    
}

Breadth first search Non-Recursive Java program

To write a Java program for level order traversal of a binary tree using a non-recursive method a queue is used. Initially root of the tree is inserted to the queue then you need to do the following until queue is empty.

Poll a node from queue and display its value.
Check if node has left child, if yes add that to the queue.
Check if node has right child, if yes add that to the queue.

Full Java program for breadth first search or level order traversal of binary tree.

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
  // first node
  private Node root;
  BFS(){
    root = null;
  }
  // Class representing tree nodes
  static class Node{
    int value;
    Node left;
    Node right;
    Node(int value){
      this.value = value;
      left = null;
      right = null;        
    }
    public void displayData(){
      System.out.print(value + " ");
    }
  }
  public void insert(int i){
    root = insert(root, i);
  }
    
  //Inserting node - recursive method
  public Node insert(Node node, int value){
    if(node == null){
      return new Node(value);
    }
    // Move to the left if passed value is 
    // less than the current node
    if(value < node.value){
      node.left = insert(node.left, value);
    }
    // Move to the right if passed value is 
    // greater than the current node
    else if(value > node.value){
      node.right = insert(node.right, value);
    }
    return node;
  }
    
  // Method to get height of the tree
  public int calculateTreeHeight(Node root){
    if(root == null){
      return 0;
    }else{
      // height of left subtree
      int lsh = calculateTreeHeight(root.left);
      // height of right subtree
      int rsh = calculateTreeHeight(root.right);
      // height in each recursive call
      return Math.max(lsh, rsh) + 1;
    }        
  }
    
  public void levelOrder(){
    int height = calculateTreeHeight(root);
    for(int i = 0; i < height; i++){
      levelOrderTraversal(root, i);
    }
  }
  // Recursive Method for breadth first search
  public void levelOrderTraversal(Node node, int level){
    if(node == null){
      return;
    }
    if(level == 0){
      System.out.print(node.value + " ");
    }else{
      levelOrderTraversal(node.left, level-1);
      levelOrderTraversal(node.right, level-1);
    }    
  }
    
  // Iterative method for breadth first search
  public void treeLevelOrderTraversal(Node root){
    if(root == null){
      return;
    }
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);
    while(!queue.isEmpty()){
      Node node = queue.poll();
      System.out.print(node.value + " ");
      if(node.left != null){
        queue.add(node.left);
      }
      if(node.right != null){
        queue.add(node.right);
      }
    }
  }
    
  public static void main(String[] args) {
    BFS bst = new BFS();
    bst.insert(50);
    bst.insert(70);    
    bst.insert(30);
    bst.insert(15);
    bst.insert(35);
    bst.insert(7);
    bst.insert(22);
    bst.insert(31);
    bst.insert(62);
    bst.insert(87);
    System.out.println("Height- " + bst.calculateTreeHeight(bst.root));
    System.out.println("Level order traversal recursive");
    bst.levelOrder();
    System.out.println("");
    System.out.println("Level order traversal iterative");
    bst.treeLevelOrderTraversal(bst.root);
    System.out.println("");
  }
}

Output

Height- 4
Level order traversal recursive
50 30 70 15 35 62 87 7 22 31 
Level order traversal iterative
50 30 70 15 35 62 87 7 22 31

That's all for this topic Binary Tree Traversal Using Breadth First Search Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Thursday, June 2, 2022