Write a program in java that reads a list of numbers from the user and lets the user

insert, delete, and search for values in the tree. The program should be menu

driven allowing for inserting, searching, and deleting from a binary search tree.

Inserting into the tree should allow for multiple inserts as follows.

$----------------------------------------$

Binary Search Tree Program

$----------------------------------------$

Make a choice...

$1)$ Insert into tree.

$2)$ Delete from tree.

$3)$ Lookup Value.

Choice? $1$

insert? $5$

insert? $2$

insert? $8$

insert? $6$

insert? $7$

insert? $9$

insert? $4$

insert? $1$

insert?

$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

$-$ Make a choice...

$1.$ Insert into tree.

$2.$ Delete from tree.

$3.$ Lookup Value.

Choice? $3$

Value? $8$

Yes, $8$ is in the tree.

$--------------------------------$

$-$Make a choice...

$1.$ Insert into tree.

$2.$ Delete from tree.

$3.$ Lookup Value.

Choice? $2$

Value? $55$

has been deleted from the tree.

$----------------------------------------$

$$Make a choice...

$1.$ Insert into tree.

$2.$ Delete from tree.

$3.$ Lookup Value.

Choice? $2$

Value? $33$

was not in the tree.