Can Someone please help me with this please:

Task:

The purpose of this assignment is to empirically measure attributes for binary search trees.

Steps:

Create a program that will build a binary search tree (BST) by adding new elements one at a time.

You may use whatever data structure you wish for this BST.

For any node in the BST, the left subtree contains keys <= the root, and the right subtree keys > the root.

Predict the average number of nodes you must visit to determine if a given key is in a BST consisting of 100 nodes, where keys are integers between 1 and 100, based on a trees height.

Use your program to create 100, 100 node BSTs by randomly adding integers between 1 and 100.

For each of these 100, randomly generated BSTs, determine (a) its height, and (b) the average number of nodes visited to determine if a key is in the tree.

Search for all values between 1 and 100.

Create, using Excel, a graph plotting tree height versus average search length, using both your predicted and empirical data.

Create a Word doc comparing your predicted average search lengths with your empirically derived values. If they differ, discuss why. If they are the same, discuss why.

Submit:

Source code

Excel workbook

Word doc summarizing experimental findings

Notes:

Feel free to add whatever you wish to the program; anything added will not impact your grade unless it hinders your completion of the required elements.