****PLEASE COMPLETE THE PROGRAM IN C++**** Thank you.

Create a Binary Search Tree (BST) of integer values, and then implement the following operations:

Traverse Inorder

Traverse Preorder

Traverse Postorder

Insert a new item (if the same item already exists, give a message already exists)

Delete an item (if the item does not exists, give a message item not found)

Assumption

Each item in the BST is unique.

Sample input/output

Initially, how many integers you want: 5

Enter the integers: 7 9 1 2 10

Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 4

Enter the item for insert: 2

This item already exists.

Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 4

Enter the item for insert: 8

This item is inserted.

Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 5

Enter the item for delete: 12

This item not found.

Page 2 of 2 Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 5

Enter the item for delete: 7

This item is deleted.

Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 1

Inorder Traverse: 1 2 8 9 10

Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 2

Preorder Traverse: 2 1 9 8 10

Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 3

Postorder Traverse: 1 8 10 9 2

Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5 for deleting an item, or 6 for exit the program: 6

Program terminated