CC-4 : Implement Breadth First Search in Binary Tree.

Description:

Implement and test a Breadth First Search in Binary Tree.

Test cases and expected outputs:

Input Parameters	Expected outputs
To Search: 8 To Search: 28	8 Found? true 28 Found? false

Pseudocode:

The node data of Tree node to be searched will be provided as input parameter to the method.

Define a Queue to temporarily hold Tree nodes as we do Breadth First search.

Add the root node of the Tree to the Queue.

While Queue size is not zero:

Extract a Tree node from the Queue.

If data of current Tree node is same as the input node data parameter to be searched, return true.

If left child node of current Tree node is not null, add it to the Queue.

If right child node of current Tree node is not null, add it to the Queue.

If we do not find the required node via above while loop then the required node is not present in the Binary Tree, so return false.

Code:

public boolean bfsSearch(BinTreeNode root, int toSearch) throws Exception{
	if (root==null) {return false;}
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	while (queue.size()!=0) {
		node=queue.poll();
		if (node.getNodeData()==toSearch) {
			return true;
		}
		if (node.getLeftChild()!=null) {
			queue.offer(node.getLeftChild());
		}	
		if (node.getRightChild()!=null) {
			queue.offer(node.getRightChild());
		}
			
	}
	return false;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

Note: for easy reference BinTreeNode is included as internal class in program below. Ideally it should be in a separate file.

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

public class BinTreeBFSSearch
{	

public boolean bfsSearch(BinTreeNode root, int toSearch) throws Exception{
	if (root==null) {return false;}
	Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
	queue.offer(root);
	BinTreeNode node=null;
	while (queue.size()!=0) {
		node=queue.poll();
		if (node.getNodeData()==toSearch) {
			return true;
		}
		if (node.getLeftChild()!=null) {
			queue.offer(node.getLeftChild());
		}	
		if (node.getRightChild()!=null) {
			queue.offer(node.getRightChild());
		}
			
	}
	return false;
}
 	
public static void main(String[] args) {
	/************************
 	Test Cases provided below
	 *************************/
	boolean retVal=false;
	try {
	BinTreeBFSSearch search=new BinTreeBFSSearch();
	BinTreeNode root=search.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(search.new BinTreeNode(5));
	root.setRightChild(search.new BinTreeNode(7));
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(search.new BinTreeNode(6));
	root.getLeftChild().setRightChild(search.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(search.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(search.new BinTreeNode(14));
	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(search.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(search.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(search.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(search.new BinTreeNode(9));
	
	retVal=search.bfsSearch(root, 8);
	System.out.println("8 Found? "+retVal);
	
	retVal=search.bfsSearch(root, 28);
	System.out.println("28 Found? "+retVal);	
	
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
	
}

public class BinTreeNode {
	private BinTreeNode leftNode=null;
private BinTreeNode rightNode=null;
private int nodeData=0;

public BinTreeNode(int data) {
	nodeData=data;
}	
public BinTreeNode getLeftChild() {
	return leftNode;
}
public void setLeftChild(BinTreeNode leftNode) {
	this.leftNode = leftNode;
}
public BinTreeNode getRightChild() {
	return rightNode;
}
public void setRightChild(BinTreeNode rightNode) {
	this.rightNode = rightNode;
}
public int getNodeData() {
	return nodeData;
}
public void setNodeData(int nodeData) {
	this.nodeData = nodeData;
}

}
	
}