deletion deleting an item from binary search tree is bit more complex than inserting new item because the location of the deletion might be anywhere in the tree (in contrastinsertions are always enacted at the bottom of path to delete an item with key kwe begin by calling treesearch(tt root)kto find the position of storing an item with key equal to if the search is successfulwe distinguish between two cases (of increasing difficulty)if has at most one childthe deletion of the node at position is easily implemented when introducing update methods for the linkedbinarytree class in section we declared nonpublic utilitydelete( )that deletes node at position and replaces it with its child (if any)presuming that has at most one child that is precisely the desired behavior it removes the item with key from the map while maintaining all other ancestor-descendant relationships in the treethereby assuring the upkeep of the binary search tree property (see figure if position has two childrenwe cannot simply remove the node from since this would create "holeand two orphaned children insteadwe proceed as follows (see figure )we locate position containing the item having the greatest key that is strictly less than that of position pthat isr before(pby the notation of section because has two childrenits predecessor is the rightmost position of the left subtree of we use ' item as replacement for the one being deleted at position because has the immediately preceding key in the mapany items in ' right subtree will have keys greater than and any other items in ' left subtree will have keys less than thereforethe binary search tree property is satisfied after the replacement having used ' as replacement for pwe instead delete the node at position from the tree fortunatelysince was located as the rightmost position in subtreer does not have right child thereforeits deletion can be performed using the first (and simplerapproach as with searching and insertionthis algorithm for deletion involves the traversal of single path downward from the rootpossibly moving an item between two positions of this pathand removing node from that path and promoting its child thereforeit executes in time (hwhere is the height of the tree