This assignment is an extension of Part 2 of Homework 3. You need to extend IntLinkedBinaryTree, which you wrote for Homework 3, in the following way:
(1). Implement a delete method whose specification is given below:
Signature: public Integer delete(Position<Integer p, Integer e)
Input:
p: the root of the tree from which a node is deleted e: the integer key of the node to be deleted
Output: Returns the deleted key, if e exists. If e does not exist, returns null.
How to delete a node from a binary search tree is described in pages 464 and 465 of the textbook.
(2). Make your program a menu driven program. When your program starts, it must display the following main menu:
Choose an option:
Add a key
Remove a key
Print the tree
Exit
If the user chooses option 1, your program performs the followings:
Prompt the user to enter an integer.
If the integer does not exist in the tree, add the integer and display an appropriate message, such as “the key added successfully,” and display the main menu.
If the integer already exists, display an appropriate message, such as “the key already exists,” and display the main menu.
If the user chooses option 2, your program performs the followings:
Prompt the user to enter an integer.
If the integer does not exist in the tree, display an appropriate message, such as “the key does not exist,” and display the main menu.
If the integer exists, display an appropriate message, such as “the key deleted successfully,” and display the main menu.
If the user chooses option 3, display all keys in the tree in increasing order, and display the main menu.
If the user chooses option 4, terminate a program.
