CC-15 : : Implement DFS Pre-order search.

Description:

Given an input integer, do a Depth First Pre-order search to check if that integer exists in any of the Binary Tree node’s node data.

Test cases and expected outputs:

Input Parameters	Expected outputs
Search:9 Search:78 Search:43	9 Found? true 78 Found? true 43 Found? false

Pseudocode:

Initialize a Stack to temporarily hold Binary Tree Nodes that are being processed in LIFO order.

Add the root node of Binary Tree to the Stack.

Iterate through stack nodes using an while loop, while Stack size is not zero:

Extract the first node of stack and assign it to a variable named parentNode.

If parentNode’s node data is equal to integer to be searched, return true.

If the parentNode’s right child is not null, add it the right child node to the Stack.

If the parentNode’s left child is not null, add it the left child node to the Stack.

Code:

public boolean dfPreOrderSearch(BinTreeNode root, int toSearch) throws Exception{
	if (root==null) {return false;}
	Deque<BinTreeNode> stack=new LinkedList<BinTreeNode>();
	stack.offerFirst(root);
	BinTreeNode parent=null;
	while (stack.size()!=0) {
		parent=stack.pollFirst();
		if (parent.getNodeData()==toSearch) {
			return true;
		}
		if (parent.getRightChild()!=null) {
			stack.offerFirst(parent.getRightChild());
		}
		if (parent.getLeftChild()!=null) {
			stack.offerFirst(parent.getLeftChild());
		}		
	}
	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.Deque;
import java.util.LinkedList;

public class BinTreeDFSPreOrderSearch {	

public boolean dfPreOrderSearch(BinTreeNode root, int toSearch) throws Exception{
	if (root==null) {return false;}
	Deque<BinTreeNode> stack=new LinkedList<BinTreeNode>();
	stack.offerFirst(root);
	BinTreeNode parent=null;
	while (stack.size()!=0) {
		parent=stack.pollFirst();
		if (parent.getNodeData()==toSearch) {
			return true;
		}
		if (parent.getRightChild()!=null) {
			stack.offerFirst(parent.getRightChild());
		}
		if (parent.getLeftChild()!=null) {
			stack.offerFirst(parent.getLeftChild());
		}		
	}
	return false;
}
 	
public static void main(String[] args) {
	/************************
 	Test cases given below:
	 ***********************/
	boolean retVal=false;
	try {
	BinTreeDFSPreOrderSearch search=new BinTreeDFSPreOrderSearch();
	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.dfPreOrderSearch(root, 9);
	System.out.println("9 Found? "+retVal);
	
	retVal=search.dfPreOrderSearch(root, 78);
	System.out.println("78 Found? "+retVal);
	
	retVal=search.dfPreOrderSearch(root, 43);
	System.out.println("43 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;
	}

}
	
}