Write a generic Java program to create a Binary Search Tree. This Binary Search Tree is to store the integer

values. Your program should display a menu of choices to operate the Binary Search Tree data structure.

Please download BSTSample before start. See the sample menu below:

$$ Insert a node $(15,5,16,3,12,20,10,13,18,23,6,7)($see Fig. $1$a$)$

$$ Find a node

$$ Delete a node $($see Fig. $1$b$,1$c$,1$d$)$

$1.$ Deleting a node with no children $(13)$

$2.$ Deleting a node with one child $(16)$

$3.$ Deleting a node with two children $(5)$

$$ Print preorder, inorder, and postorder traversal

Figure $1$: $($a$)$ Binary Search Tree after inserting all the values; $($b$)$ Binary Search Tree after deleting $13$; $($c$)$

Binary Search Tree after deleting $16$; $($d$)$ Binary Search Tree after deleting $5$

Please note that you will not get any credit if you do not implement generic recursive versions

of binary search tree operations with the above$-$mentioned criteria.

Here is a sample execution of the program:

After Insertion:

Preorder traversal: $15531210671316201823$

Inorder traversal: $35671012131516182023$

Postorder traversal: $37610131251823201615$

$=====================$

After deleting:

Preorder traversal: $155312106716201823$

Inorder traversal: $356710121516182023$

Postorder traversal: $376101251823201615$

$=====================$

After deleting:

Preorder traversal: $1553121067201823$

Inorder traversal: $3567101215182023$

Postorder traversal: $3761012518232015$

$=====================$

After deleting:

Preorder traversal: $156312107201823$

Inorder traversal: $367101215182023$

Postorder traversal: $371012618232015$

$=====================$Objective:

The objective of this assignment is to practice and implement binary search tree operations.

Problem Specification:

Write a generic Java program to create a Binary Search Tree. This Binary Search Tree is to store the integer

values. Your program should display a menu of choices to operate the Binary Search Tree data structure.

Please download BSTSample before start. See the sample menu below:

Insert a node $(15,5,16,3,12,20,10,13,18,23,6,7)($see Fig. $1$a$)$

Find a node

Delete a node $($see Fig. $1$b$,1$c$,1$d$)$

Deleting a node with no children $(13)$

Deleting a node with one child $(16)$

Deleting a node with two children $(5)$

Print preorder, inorder, and postorder traversal

Figure $1$: $($a$)$ Binary Search Tree after inserting all the values; $($b$)$ Binary Search Tree after deleting $13$; $($c$)$

Binary Search Tree after deleting I$6$; $($d$)$ Binary Search Tree after deleting $5$

Plense note that you will not get any credit if you do not implement generic recursive versions

of binary search tree operutions with the above$-$mentioned criteria.

Here is a sample execution of the program:

After Insertion:

Preorder traversal: $15531210671316201823$

Inorder traversal: $356671012131516,1820,23$

Postorder travensal: $37610131251823201615$

After deleting:

Preorder traversal: $155312106716201823$

Inorder traversal: $356671012151618,2023$

Postorder traversal: $3761012518,232016,15$

After deleting:

Preorder travenal: $1553121067201823$

Inorder traversal: $3566710,121518,2023$

Postorder travensal: $3761012518232015$

After deleting:

Preorder traversal: $156312107201823$

Inorder traversal: $36710,121518,20,23$

Postorder travenal: $3710,1261823,2015$