Homework 7: Binary Search Tree

Due: 2:10pm, Friday, October 23. Submit your solution (consisting of BinarySearchTree.java only) using the Sauron Submission System. [instructions]

In this assignment you'll be implementing and testing a Binary Search Tree as we discussed in class. I've included the file TreeNode.java and BinarySearchTree.java to get you started.

The following instance methods should be implemented:

---

public boolean contains(E value)

Returns true if value exists in the BST, false if it does not.

public boolean add(E value)

Adds value to the BST, returning true if successful or false if value already exists

public void print()

Prints all elements in the BST in order

public E minimum()

Returns the smallest element in the tree

public E maximum()

Returns the largest element in the tree

public E successor(E value)

Returns the element immediately after value in the tree or null if value is the largest element. Note that value is NOT required to be in the tree.

public E predecessor(E value)

Returns the element immediately before value in the tree or null if value is the smallest element. Note that value is NOT required to be in the tree.

---

You should comment in your code the Big-O analysis of each method. You will be graded on correctness, style, and the efficiency of your algorithms.