This is a java problem which using ADT Binary Search Tree. I need the fully completed code with Driver class. I also want to know how to create a file which used to read by the program. since the program will read a file and sort the data.Thank you!

This lab will give you practice working with a binary search tree, and write a recursive method to access the items in a binary search tree.

Lab

1) A binary search tree may be displayed horizontally using recursion. Here is the rough algorithm:

if (root is not empty)

{

Print right subtree, increasing indentation by one level

Print contents of root

Print left subtree, increasing indentation by one level

}

Add a display method to the BinarySearchTree class (pages 616-618), which in turn calls a recursive helper method:

-printTree(in root:TreeNode, in indentation:integer)

2) Write a program that uses the modified BinarySearchTree class to perform tree sort. Your program should (a) read input from a file, (b) build the binary search tree from the input, (c) display the binary search tree using the method described in part 1, and (d) display the sorted items.

input.dat contents:

January

February

March

April

May

June

July

August

September

October

November

December

Sample program dialog:

Tree sort program

Enter name of input file: input.dat

Binary search tree:

September

October

November

May

March

June

July

January

February

December

August

April

Sorted items:

April

August

December

February

January

July

June

March

May

November

October

September

The BinarySearchTree class (pages 616-618) is below:

616 Chapter 11 Trees The methods could be privat but making them protected en class to use them directly import SearchKeys.KeyedItem; // ADT binary search tree. // Assumption: A tree contains at most one item wi given search key at any time. public class BinarySearchTreexr extends KeyedIteme KT extends Comparablex? supe extends BinaryTreeBasis // inherits isEmpty(), makeEmpty), getRootItem(), a // the use of the constructors from BinaryTreeBas i and public BinarySearchTree() I end default constructor public BinarysearchTree(T rootItem) super (rootItem) ; / end constructor public void setRootItem(T newItem) throws UnsupportedoperationException ( throw new UnsupportedoperationException ) // end setRootItenm public void insert (T newItem) t root insertitem( root, newItem) ; I end insert public T retrieve (KT searchkey) return retrieveItem( root, searchKey): I/ end retrieve public void delete(KT searchKey) throws TreeException t root = delete Item(root, / end delete searchKey); public void delete(T item) throws TreeException t root - deleteItem(root, item. getkey O)i // end delete protected TreeNode insertItem(TreeNode T newitem) ( TreeNode newSubtree; if (tHode null)