trees let (nbe the average number of full nodes in an -node binary search tree determine the values of ( and ( show that for - ( (if( ) - (ni= show (by inductionthat ( ( )/ is solution to the equation in part ( )with the initial conditions in part (ad use the results of exercise to determine the average number of leaves in an -node binary search tree write an implementation of the set classwith associated iterators using binary search tree add to each node link to the parent node write an implementation of the map class by storing data member of type set write an implementation of the set classwith associated iterators using binary search tree add to each node link to the next smallest and next largest node to make your code simpleradd header and tail node which are not part of the binary search treebut help make the linked list part of the code simpler suppose you want to perform an experiment to verify the problems that can be caused by random insert/remove pairs here is strategy that is not perfectly randombut close enough you build tree with elements by inserting elements chosen at random from the range to an you then perform pairs of insertions followed by deletions assume the existence of routinerandominteger( , )which returns uniform random integer between and inclusive explain how to generate random integer between and that is not already in the tree (so random insertion can be performedin terms of and awhat is the running time of this operationb explain how to generate random integer between and that is already in the tree (so random deletion can be performedwhat is the running time of this operationc what is good choice of awhywrite program to evaluate empirically the following strategies for removing nodes with two childrena replace with the largest nodexin tl and recursively remove alternately replace with the largest node in tl and the smallest node in tr and recursively remove the appropriate node replace with either the largest node in tl or the smallest node in tr (recursively removing the appropriate node)making the choice randomly which strategy seems to give the most balancewhich takes the least cpu time to process the entire sequenceredo the binary search tree class to implement lazy deletion note carefully that this affects all of the routines especially challenging are findmin and findmaxwhich must now be done recursively