Write a Breadth First Search Algorithm in Java

1 package com.techieprogrammer;
2 import java.util.ArrayList;
3 import java.util.Arrays;
4 import java.util.Iterator;
5 import java.util.List;
6 
7 class BFSNode {
8     int nodeValue;
9     BFSNode leftChildNode;
10     BFSNode rightChildNode;
11     
12     public BFSNode(int nodeValue) {
13         this.nodeValue = nodeValue;        //Place to update node value through constructor for each Node
14         this.leftChildNode = null;
15         this.rightChildNode = null;
16     }
17 }
18 
19 class  BFSCompute {
20     private static BFSNode temp;
21     private static BFSNode newNode;
22     private static BFSNode headNode;
23     private static List <BFSNode> nodeBuffer = new ArrayList<BFSNode>();
24     
25     public static void add(int nodeValue) {
26         newNode = new BFSNode(nodeValue);
27         temp = headNode;
28         if(temp != null) 
29         {    mapping();    }
30         else 
31         {    headNode = newNode; }
32     }
33     
34     private static void mapping() {
35         if(newNode.nodeValue < temp.nodeValue) {     //Check value of new Node is smaller than Parent Node
36             if(temp.leftChildNode == null)             
37             {    temp.leftChildNode = newNode;    }    //Assign new Node to leftChildNode of Parent Node
38             else
39             {
40                 temp = temp.leftChildNode;            //Parent Node is already having leftChildNode,so temp object reference variable is now pointing leftChildNode as Parent Node
41                 mapping();
42             }
43         }
44         else
45         {
46             if(temp.rightChildNode == null) 
47             {    temp.rightChildNode = newNode;    }    //Assign new Node to rightChildNode of Parent Node
48             else
49             {
50                 temp = temp.rightChildNode;            //Parent Node is already having rightChildNode,so temp object reference variable is now pointing rightChildNode as Parent Node
51                 mapping();
52             }
53         }
54     }
55     
56     public static void traversal() {
57         if(headNode != null) {
58             System.out.println("Breadth First Search Traversal:");
59             nodeBuffer.add(headNode);                //Add head Node is nodeBuffer ArrayList
60             compute();
61         }
62     }
63     
64     //Flow Travels from Left to Right Order, so that leftChildNode is added before rightChildNode in nodeBuffer ArrayList
65     private static void compute() {
66         int counter = 0;
67         int nodeBufferSize = 0;
68         do
69         {
70             System.out.print(nodeBuffer.get(counter).nodeValue+" ");
71             if(nodeBuffer.get(counter).leftChildNode != null) {
72                 nodeBuffer.add(nodeBuffer.get(counter).leftChildNode);
73             }
74             if(nodeBuffer.get(counter).rightChildNode != null) {
75                 nodeBuffer.add(nodeBuffer.get(counter).rightChildNode);
76             }
77             counter++;
78             nodeBufferSize = nodeBuffer.size();
79         }
80         while(counter < nodeBufferSize);
81     }
82 }
83 
84 public class BreadthFirstSearch {
85     //Entry Point
86     public static void main(String[] args) {
87         List <Integer> intList = new ArrayList <Integer>(Arrays.asList(50,2,5,78,90,20,4,6,98));   
88         Iterator<Integer> ptr  = intList.iterator();
89         while(ptr.hasNext()) 
90         {    BFSCompute.add(ptr.next());     }
91         BFSCompute.traversal();
92     }
93 }