In Java Please

Problem: Write a program to do the following:

(We are measuring the Running time in nano seconds that it took the program to run) and displaying how long it took for each search

The way that data is stored in a Binary Search Tree (BST) depends on the order in which the values are inserted. For example, if we insert the numbers 1, 2, 3 in that order, the resulting tree has 1 in the root, 2 as a right child of the root, and 3 as a right child of 2. However, if we insert first 2, then 2 will be stored in the root, and 1 and 3 will be the left and right child of the root respectively. Moreover, not only the values are stored in different places but also the shape of the tree obtained is different. The first one is skewed whereas the second one is balanced. As a consequence, although both trees contain the same data, the worst-case cost of searching differs. The purpose of this assignment is to highlight this striking difference in running time, creating a skewed BST and a (roughly) balanced BST, both with a large number of nodes, and measuring the execution time of searching on each. Input an integer r. (Should work with "big" numbers.) Create a completely-skewed BST S containing 1, 2, ..., X. Create a BST R containing r integers without repetitions gen- erated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by a big number.) Given that the numbers are generated uniformly at random, the tree will likely be balanced. Measure the time to search in S for a number that is not in the tree. Measure the time to search in R for a new random number. Display the time taken for each search. The way that data is stored in a Binary Search Tree (BST) depends on the order in which the values are inserted. For example, if we insert the numbers 1, 2, 3 in that order, the resulting tree has 1 in the root, 2 as a right child of the root, and 3 as a right child of 2. However, if we insert first 2, then 2 will be stored in the root, and 1 and 3 will be the left and right child of the root respectively. Moreover, not only the values are stored in different places but also the shape of the tree obtained is different. The first one is skewed whereas the second one is balanced. As a consequence, although both trees contain the same data, the worst-case cost of searching differs. The purpose of this assignment is to highlight this striking difference in running time, creating a skewed BST and a (roughly) balanced BST, both with a large number of nodes, and measuring the execution time of searching on each. Input an integer r. (Should work with "big" numbers.) Create a completely-skewed BST S containing 1, 2, ..., X. Create a BST R containing r integers without repetitions gen- erated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by a big number.) Given that the numbers are generated uniformly at random, the tree will likely be balanced. Measure the time to search in S for a number that is not in the tree. Measure the time to search in R for a new random number. Display the time taken for each search