In Java, implement a Binary Search Tree in an array. (Except we will not have need to delete anything.) I will provide you with an array class that you must use to implement your BST. My class is based on an ArrayList, but takes care of accessing nodes beyond the end of the array. (With any set or get, I increase the size if necessary and fill with nulls.)

You may not use a linked implementation. You will use 2i+1, 2i+2, and (i-1)/2 to traverse the tree.

The data will be a text file containing words. Assume a word is whatever is returned by the Scanner.next() method. Duplicate words will be ignored.

Open a file called GA.txt. Using the Scanner class, read each word, convert to uppercase, and

1. insert it into a BST

2. use a BST method to find and print the minimum value

3. use a BST method to find and print the maximum value

4. print the tree inorder

5. print the tree preorder

6. print the tree postorder

BST methods that you should implement: empty(), insert(String), min(), max(), inOrder(), preOrder(), and postOrder(), along with the following utility methods leftChild(int), rightChild(int), parent(int), and toString().

Dont forget to use compareTo for your strings.

--------------------------------------------------------

Sample input: eee bbb xxx aaa ccc yyy zzz ddd

Sample output (with the array shown for debugging):

[EEE, BBB, XXX, AAA, CCC, null, YYY, null, null, null, DDD, null, null, null, ZZZ]

min: AAA

max: ZZZ

inorder:

AAA

BBB

CCC

DDD

EEE

XXX

YYY

ZZZ

preorder:

EEE

BBB

AAA

CCC

DDD

XXX

YYY

ZZZ

postorder:

AAA

DDD

CCC

BBB

ZZZ

YYY

XXX

EEE

Fourscore and seven years ago our fathers brought forth on this continent a new nation conceived in

Liberty and dedicated to the proposition that all men are created equal

min: A

max: YEARS

inorder:

A

AGO

ALL

AND

ARE

BROUGHT

CONCEIVED

CONTINENT

CREATED

DEDICATED

EQUAL

FATHERS

FORTH

FOURSCORE

IN

LIBERTY

MEN

NATION

NEW

ON

OUR

PROPOSITION

SEVEN

THAT

THE

THIS

TO

YEARS

preorder:

FOURSCORE

AND

AGO

A

ALL

FATHERS

BROUGHT

ARE

CONTINENT

CONCEIVED

DEDICATED

CREATED

EQUAL

FORTH

SEVEN

OUR

ON

NEW

NATION

IN

LIBERTY

MEN

PROPOSITION

YEARS

THIS

THE

THAT

TO

postorder:

A

ALL

AGO

ARE

CONCEIVED

CREATED

EQUAL

DEDICATED

CONTINENT

BROUGHT

FORTH

FATHERS

AND

MEN

LIBERTY

IN

NATION

NEW

ON

PROPOSITION

OUR

THAT

THE

TO

THIS

YEARS

SEVEN

FOURSCORE

--------------------------------------------------------------------------

HERE IS SOME OF THE CODE:

import java.util.ArrayList; /* This class is to be used as the basis for your BST class * Declare, construct and use a pmmArrayList in your BST * (this is composition, as opposed to inheritance) * YOU MAY NOT CHANGE THIS CODE... * I will use my own copy of this code, not yours. * If someone finds an error, I will post a fix for everyone to use. */ public class pmmArrayList
 { private ArrayList
 A; // I modify some arraylist methods and don't implement many of them public pmmArrayList() { A = new ArrayList
(); } // we won't be deleting anything... I was just thinking ahead public boolean empty() { return (A.isEmpty() || A.get(0) == null ? true : false); } // returns the value stored, or null public dt get(int indx) { growIfNeeded(indx); return A.get(indx); } // an arraylist adds an element by shifting all the others // which we don't want, hence changed to a set // you can "add" at any location (like a JavaScript array) public void add(int indx, dt e) { growIfNeeded(indx); A.set(indx, e); } // except for returning a value, the same as "add" // the array grows as necessary to accomodate the index public dt set(int indx, dt e) { growIfNeeded(indx); return A.set(indx, e); } // returns the number of non-null values stored public int size() { int cnt = 0; for (dt i: A) if (i != null) cnt++; return cnt; } public String toString() { return A.toString(); } private void growIfNeeded(int current) { A.ensureCapacity(current+1); for(int i = A.size(); i <= current; i++) A.add(i,null); } }