destructor and copy constructor as usualthe destructor calls makeempty the public makeempty (not shownsimply calls the private recursive version as shown in figure after recursively processing ' childrena call to delete is made for thus all nodes are recursively reclaimed notice that at the endtand thus rootis changed to point at nullptr the copy constructorshown in figure follows the usual procedurefirst initializing root to nullptr and then making copy of rhs we use very slick recursive function named clone to do all the dirty work average-case analysis intuitivelywe expect that all of the operations described in this sectionexcept makeempty and copyingshould take (log ntimebecause in constant time we descend level in the treethus operating on tree that is now roughly half as large indeedthe running time of all the operations (except makeempty and copyingis ( )where is the depth of the node containing the accessed item (in the case of removethis may be the replacement node in the two-child casewe prove in this section that the average depth over all nodes in tree is (log non the assumption that all insertion sequences are equally likely the sum of the depths of all nodes in tree is known as the internal path length we will now calculate the average internal path length of binary search treewhere the average is taken over all possible insertion sequences into binary search trees /*destructor for the tree *~binarysearchtreemakeempty)/*internal method to make subtree empty *void makeemptybinarynode ift !nullptr makeemptyt->left )makeemptyt->right )delete tt nullptrfigure destructor and recursive makeempty member function