Please help with this JAVA program. Thank you!

In this programming project you will practice the implementation of binary search trees. Download the attached ZIP le for a starting place; it includes several interfaces and partial implementations that are base for this ADT. You would only need to change three les: ArrayUnorderedList, LinkedBinaryTree, and LinkedBinarySearchTree (should contain testing code).

Complete the implementation of ArrayList. Speci cally, implement these methods: removeFirst and removeLast. Don't neglect support for the iterator in ArrayList. Do not import any packages other than those already imported. [8 points]

2

Complete the implementation of ArrayUnorderedList. Speci cally, implement these methods: ad- dToFront and addToRear. Don't neglect support for the iterator in ArrayList. Do not import any packages other than those already imported.

Complete the implementation of LinkedBinaryTree. Speci cally, implement these methods: get- RootElement(), getRootNode(), getLeft(), getRight(), size(), getHeight(), height(), contains(), toString(), and iteratorPreOrder(). Review the comments in LinkedBinaryTree and BinaryTreeADT for imple- mentation requirements.

[LC PP 11.2 modi ed] The LinkedBinarySearchTree class is currently using the nd and contains methods of the LinkedBinaryTree class via inheritance. This is not optimal! Implement these two methods for the LinkedBinarySearchTree class, nd() and contains(), so that they will be more e cient by making use of the ordering property of a binary search tree. Notice that ve other methods in LinkedBinarySearchTree are not yet implemented: removeMax(), ndMin(), ndMax(), getLeft(), getRight(), ndNode(). If any are needed by your algorithms, implement them, otherwise you may omit them.

Lastly, write appropriate testing documentation - see next section. [10 points]

PLEASE find array unordered list below