This exercise is intended to demonstrate building a binary tree to be used as a binary search tree, a BST.

You are to write a Java program that has at least one function: main. main will be the entry point/driver of your program.

Your program should define two classes, BinaryNode and BSTTree. BinaryNode should define the individual nodes to be used in your BST. It should have private attributes for an integer payload, reference variables for two children per node, and reference variable(s) that allows you to traverse your tree both from root to leaf and from leaf to root.

BSTTree should provide the structure for your binary tree. It should have attributes to allow addressability to the root of the tree and to track the number of nodes in the tree. BSTTree should also implement the functionality to allow the tree to operate as a simple BST. One, it should allow nodes to be added to the tree as required for a BST. Two, it should allow the tree to be searched for any given integer value with a binary search. It should report whether or not the integer is found in a node of the tree and how many comparison it took to make that determination.

Two data files will be provided. BSTInput.txt contains a list pf payload values for your tree. If nodes are added to the tree in the order these values are read from the file, your tree will be complete. You will not be asked to remove a node from the tree, so there will be no need for you to implement rebalancing functionality.

The second file, BSTTreeSearch.txt, contains a list of integers. After the payload nodes have been loaded into your tree, you should use the search functionality to determine if the integers in this search list are in the tree or not.

Your program should work for input files of any size. Your program should not be dependent on the sequence of the search list. When executing your program In NetBeans, the working directory is the directory of your project. To facilitate us evaluating your work, add the two data files to your project directory. Do not change the file names. All internal references to the files in your program should be the file name only. Do not include the full path.

You should print a clearly labeled, formatted report of your results. It should include the payload values loaded into your tree, the total number of nodes in your tree, whether each item in the search list was found in the tree or not, and how many comparisons were required to find it or determine that it was not there.

Submit your work as a .zip file as detailed in the Lab Submission Guidelines document.