trees /*copy constructor *binarysearchtreeconst binarysearchtree rhs rootnullptr root clonerhs root )/*internal method to clone subtree *binarynode clonebinarynode * const ift =nullptr return nullptrelse return new binarynodet->elementclonet->left )clonet->right }figure copy constructor and recursive clone member function let (nbe the internal path length for some tree of nodes ( an -node tree consists of an -node left subtree and an ( )-node right subtreeplus root at depth zero for < (iis the internal path length of the left subtree with respect to its root in the main treeall these nodes are one level deeper the same holds for the right subtree thuswe get the recurrence (nd(id( if all subtree sizes are equally likelywhich is true for binary search trees (since the subtree size depends only on the relative rank of the first element inserted into the tree)but not binary treesthen the average value of both (iand ( is ( /nn- = djthis yields - (ndjn = this recurrence will be encountered and solved in obtaining an average value of (no( log nthusthe expected depth of any node is (log nas an examplethe randomly generated -node tree shown in figure has nodes at expected depth it is tempting to say immediately that this result implies that the average running time of all the operations discussed in the previous section is (log )but this is not entirely true the reason for this is that because of deletionsit is not clear that all binary search trees are equally likely in particularthe deletion algorithm described above favors making the left subtrees deeper than the rightbecause we are always replacing deleted node with node from the right subtree the exact effect of this strategy is still unknownbut