will be insert( , ->leftor insert( , ->righteither wayt is now reference to either ->left or ->rightmeaning that ->left or ->right will be changed to point at the new node all in alla slick maneuver remove as is common with many data structuresthe hardest operation is deletion once we have found the node to be deletedwe need to consider several possibilities if the node is leafit can be deleted immediately if the node has one childthe node can be deleted after its parent adjusts link to bypass the node (we will draw the link directions explicitly for claritysee figure the complicated case deals with node with two children the general strategy is to replace the data of this node with the smallest data of the right subtree (which is easily foundand recursively delete that node (which is now emptybecause the smallest node in the right subtree cannot have left childthe second remove is an easy one figure shows an initial tree and the result of deletion the node to be deleted is the left child of the rootthe key value is it is replaced with the smallest data in its right subtree ( )and then that node is deleted as before the code in figure performs deletion it is inefficient because it makes two passes down the tree to find and delete the smallest node in the right subtree when this is appropriate it is easy to remove this inefficiency by writing special removemin methodand we have left it in only for simplicity if the number of deletions is expected to be smallthen popular strategy to use is lazy deletionwhen an element is to be deletedit is left in the tree and merely marked as being deleted this is especially popular if duplicate items are presentbecause then the data member that keeps count of the frequency of appearance can be decremented if the number of real nodes in the tree is the same as the number of "deletednodesthen the depth of the tree is only expected to go up by small constant (why?)so there is very small time penalty associated with lazy deletion alsoif deleted item is reinsertedthe overhead of allocating new cell is avoided figure deletion of node ( with one childbefore and after