Question

Scenario

Implement an algorithm that searches the binary tree one level at a time, left to right. The traversal starts from the root node and finishes at the leaf node.

Aim

Apply BFS traversal in Java.

Steps for Completion

1. Implement the psuedocode algorithm from Snippet 3.14 (shown below) in a public method called printBfs()in SimpleBinaryTree. The return value should be void and it should print each node on a newline.

breadthFirstSearch(root)
    if (root != null)
        queue = createQueue()
        enqueue(queue, root)
        while (not isEmpty(queue))
            node = dequeue(queue)
            process(node)
            if(node.left != null) enqueue(queue, node.left)
            if(node.right != null) enqueue(queue, node.right)

^{Snippet 3.14}

Answer 1

//Java program

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

class Node{
   public int key;
   public Node left,right;  
  
   public Node(int data) {
       key = data;
       left = null;
       right = null;
   }
}

public class BFS {
   public static void printBfs(Node root) {
       if(root == null)return;
       Queue<Node> queue = new LinkedList<>();
       queue.add(root);
       while(queue.size()!=0) {
           Node temp = queue.remove();
           System.out.println(temp.key);
           if(temp.left!=null)queue.add(temp.left);
           if(temp.right!=null)queue.add(temp.right);
       }
      
   }
  
   public static void main(String args[]) {
       Node root = new Node(1);
       root.left = new Node(2);
       root.right = new Node(3);
       root.left.left = new Node(4);
       root.left.right = new Node(5);
      
       printBfs(root);
   }
}