with binary search tree is bit more complexsince we do not wish to create any "holesin the tree we assumein this casethat proper binary tree supports the following additional update operationremoveexternal( )remove an external node and its parentreplacing ' parent with ' siblingan error occurs if is not external given this operationwe begin our implementation of operation remove(kof the dictionary adt by calling treesearch(kt root()on to find node of storing an entry with key equal to if treesearch returns an external nodethen there is no entry with key in dictionary dand we return null (and we are doneif treesearch returns an internal node insteadthen stores an entry we wish to removeand we distinguish two cases (of increasing difficulty)if one of the children of node is an external nodesay node zwe simply remove and from by means of operation removeexternal(zon this operation restructures by replacing with the sibling of zremoving both and from (see figure if both children of node are internal nodeswe cannot simply remove the node from tsince this would create "holein insteadwe proceed as follows (see figure )we find the first internal node that follows in an inorder traversal of node is the left-most internal node in the right subtree of wand is found by going first to the right child of and then down from therefollowing left children alsothe left child of is the external node that immediately follows node in the inorder traversal of we save the entry stored at in temporary variable tand move the entry of into this action has the effect of removing the former entry stored at we remove nodes and from by calling removeexternal(xon this action replaces with ' siblingand removes both and from we return the entry previously stored at wwhich we had saved in the temporary variable as with searching and insertionthis removal algorithm traverses path from the root to an external nodepossibly moving an entry between two nodes of this pathand then performs removeexternal operation at that external node