and the following method to the BinarySearchTree class:
Returns the height of the tree, i.e., the length of the longest path from the root to a leaf.
Returns the weight of the tree, i.e., the sum of all the node depths.
Note: all three methods should return 0 if applied to an empty tree. Be sure to test your methods thoroughly before continuing.
Returns the average cost of a search in the tree, i.e., weight/size.
Your program should display the average of these heights and costs over all of the constructed trees, as well as the minimum possible tree height (⌈log2(N+1)⌉). For example,
|number of values (N)||min possible height||average tree height||average search cost|
|N = 1,000|
|N = 2,000|
|N = 4,000|
|N = 8,000|
|N = 16,000|
|N = 32,000|