This assignment is an extension of Homework 3. In Homework 3, you implemented a generic binary search tree MyBST and implemented an add method in it.

For this assignment, you are required to implement the following methods.

Algorithm successor(p)

Input parameter:

p: The position of the node whose successor is searched

Output:

Returns the position of the successor of p

If there is no successor of p in the tree, returns null.

Note: Let e be the element of p. The successor of p is the node which has the smallest element that is larger than e. In other words, if we list all nodes in the tree in increasing order of elements, the ps successor is located immediately after p.

Algorithm predecessor(p)

Input parameter:

p: The position of the node whose predecessor is searched

Output:

Returns the position of the predecessor of p

If there is no predecessor of p in the tree, returns null.

Note: Let e be the element of p. The predecessor of p is the node which has the largest element that is smaller than e. In other words, if we list all nodes in the tree in increasing order of elements, the ps predecessor is located immediately before p.

Algorithm delete(p, e)

Input parameters:

p: The position of the root of the tree (or subtree) from which

the node with the element e is to be deleted

e: The element of the node to be deleted

Output:

Returns e if a node with e exists.

If there is no node with e in the tree, returns null.

Note: You must implement the delete method that is described in pages 464-465 of the textbook. Otherwise, you will lose points even if your implementation deletes a given node correctly.

Documentation

No separate documentation is needed. However, you must include sufficient inline comments within your program.

Grading

The successor method will be tested three times and 3 points will be deducted for each wrong result.

The predecessor method will be tested three times and 3 points will be deducted for each wrong result.

The delete method will be tested three times and 5 points will be deducted for each wrong result.

Points will be deducted up to 20 points if you do not include sufficient inline comments.

Deliverables

You need to submit a revised the MyBST.java file. Combine this file with all other files, which are necessary to compile and execute your program, into a single archive file, such as a zip file or a rar file, and name it LastName_FirstName_hw5.EXT, where EXT is an appropriate file extension (such as zip or rar). Upload it to Blackboard.