Implement a balanced binary search tree

Step 1:
Implement a BST with integer based nodes.
Step 2:
IGNORE
Step 3:
Insert 150K random numbers into std::list, std::vector, array (use malloc), and BST. Make sure the same numbers are inserted into each.
Step 4:
Present the user with a simple menu:
Select an option:
1) Search for a number all data structures
2) Exit
Enter in option (1–2):
If the user selects 1, the user is asked to input a number. This number is searched for in all data structures recording how long it takes in milliseconds to do each. If the number is found in the structures, display the time taken to find it in each structure. If
not, let the user know that the number could not be found in any of them and still show the time to complete the search on each structure.