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

$1551620101318233126$

$7$

$($a$)$

$15516201018233126$

$7$

$($b$)$

$155201823103126$

$7$

$($c$)$

$156201823103127$

$($d$)$

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$

COSC$2007$O$24$W: Assignment$-4$

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$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 $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$