Answer Happy

1. Create a Java program that prompts the user the initialchoices for the Binary Search Treea. User chooses
1: Insert, User chooses
2: Delete, User chooses
3: Show BinaryTree, User chooses
4: Exit Program
2. Insertion in a tree should be such that it obeys the mainproperties of the binary searchtree. The basic algorithm should be:a. If the node to be inserted is greater than the existing root,move down a levelthrough the right pointer of the root.b. If the node to be inserted is lesser than the existing root,move down a levelthrough the left pointer of the root.c. Repeat this process for all nodes till the leaves arereached.d. Insert the node as the left or right pointer for the leaf (basedon its value - if it issmaller than the leaf, it should be inserted as the left pointer;if it is larger than theleaf, it should be inserted as the right pointer)
3. Deletion is a bit more complicated than insertion because itvaries depending on the nodethat needs to be deleted from the tree.a. If the node has no children (that is, it is a leaf) - it cansimply be deleted from thetree.b. If the node has one child, simply delete the node and move thechild up to replaceit.c. If the node has two children, it becomes a little tricky. Weneed to find the nodewhich has the smallest value in the right subtree (among theelements that have agreater value than the node to be deleted) for the node and usethat to replace thedeleted node. (Note that the smallest value in the right subtree isthe node thatcomes immediately after the node to be deleted, implying that it isthe inordersuccessor for the node to be deleted).
If the user chooses to delete an element from the Binary SearchTree:a. Display the elements in the binary treeb. Prompt the user to enter an element to be deleted.c. After entering a number to be deleted, show the updated elementscontained inthe binary tree.
d. Example:
4. If the user will choose: Show Binary Search Tree your outputshould look like this:Sample Output:
Sample Output: 1. Insert 2. Delete 3. Show Binary Tree 4. Exit Program Write your input: 1 Write the elements for insertion delimited by spaces(ex: 2 1 4 3 5).
1 2 3 4 5
3 5 8 7 9
3 8 7 9
Write your input: 3 Binary Search Tree 8 /\ 59 3 7