binary search tree usage write a program to

Question

Binary Search Tree usage:

Write a program to compare the time taken for a search in a skewed tree, a balanced tree, and a random tree. Specically, your program should do the following.

• Input an integer x. (Should work with big numbers, such as 10⁶.)
• Create a completely-skewed binary search tree S containing 1; 2; : : : ; x.
• Create a completely-balanced binary search tree B containing the same numbers. (You can use the same idea of the level-order method to insert the numbers in the order needed to obtain the tree balanced.)
• Create a binary search tree R containing x integers generated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by 10⁶.)
• Search for a leaf in S and B, and for a new random number in R, and show the time taken for each search in the screen.