CC-3 : Implement Breadth First Traversal of Binary Tree using recursion.

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.ArrayList;

public class BinTreeBfsRecursive {

private ArrayList<Integer> bfsTraversal=new ArrayList<Integer>();
public ArrayList<Integer> getBfs() {
	return bfsTraversal;
}
public void setBfs(ArrayList<Integer> bfsTraversal) {
	this.bfsTraversal = bfsTraversal;
}

public void bfs(BinTreeNode root) {
	int maxlevel= maxLevel(root);
	for (int lvl=1; lvl<=maxlevel; lvl++) {
		bfsLevelwise(root, lvl);
	}
}

public void bfsLevelwise(BinTreeNode root, int lvl) {
	if (root==null) {return;}
	if (lvl==1) {
		bfsTraversal.add(root.getNodeData());		
	}else {
		bfsLevelwise(root.getLeftChild(), lvl-1);
		bfsLevelwise(root.getRightChild(), lvl-1);
	}
}

public int maxLevel(BinTreeNode root) {
	if (root==null) {return 0;}
	else {
		int leftLevel=maxLevel(root.getLeftChild());
		int rtLevel=maxLevel(root.getRightChild());
		if(leftLevel > rtLevel) {
			return leftLevel+1;
		}else {
			return rtLevel+1;
		}		
	}
}

public static void printArrayListSummary(ArrayList al, String label) throws Exception {
	if (al == null) { System.out.println("\n\n Input ArrayList was null !! \n"); return; }
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < al.size(); arrayIndex++) {
			System.out.print(al.get(arrayIndex));
			if (arrayIndex < al.size()-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println("************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}
 	
public static void main(String[] args) {
	/***********************
 	Test cases given below:
	 ***********************/
	ArrayList<Integer> retVal=null;
	try {
	BinTreeBfsRecursive bfs=new BinTreeBfsRecursive();
	BinTreeNode root=bfs.new BinTreeNode(4);
	//Left L1 Children
	root.setLeftChild(bfs.new BinTreeNode(5));
	root.setRightChild(bfs.new BinTreeNode(7));
	
	//Left L2 Children
	root.getLeftChild().setLeftChild(bfs.new BinTreeNode(6));
	root.getLeftChild().setRightChild(bfs.new BinTreeNode(78));
	
	//Left L3 Children
	root.getLeftChild().getLeftChild().setLeftChild(bfs.new BinTreeNode(33));
	
	//Right L2 Children
	root.getRightChild().setLeftChild(bfs.new BinTreeNode(14));
	
	
	//Right L3 Children
	root.getRightChild().getLeftChild().setLeftChild(bfs.new BinTreeNode(8));
	root.getRightChild().getLeftChild().setRightChild(bfs.new BinTreeNode(16));
	
	//Right L3 Children
	root.getRightChild().getLeftChild().getRightChild().setLeftChild(bfs.new BinTreeNode(18));
	
	//Right L4 Children
	root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(bfs.new BinTreeNode(9));
	
	
	bfs.bfs(root);
	printArrayListSummary(bfs.getBfs(), "Bfs traversal");	
	
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}

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;
}

}
	
}