binary search trees in we introduced the tree data structure and demonstrated variety of applications one important use is as search tree (as described on page in this we use search tree structure to efficiently implement sorted map the three most fundamental methods of map (see section arem[ ]return the value associated with key in map mif one existsotherwise raise keyerrorimplemented with getitem method [kvassociate value with key in map mreplacing the existing value if the map already contains an item with key equal to kimplemented with setitem method del [ ]remove from map the item with key equal to kif has no such itemthen raise keyerrorimplemented with delitem method the sorted map adt includes additional functionality (see section )guaranteeing that an iteration reports keys in sorted orderand supporting additional searches such as find gt(kand find range(startstopbinary trees are an excellent data structure for storing items of mapassuming we have an order relation defined on the keys in this contexta binary search tree is binary tree with each position storing key-value pair (kvsuch thatkeys stored in the left subtree of are less than keys stored in the right subtree of are greater than an example of such binary search tree is given in figure as matter of conveniencewe will not diagram the values associated with keys in this since those values do not affect the placement of items within search tree figure binary search tree with integer keys we omit the display of associated values in this since they are not relevant to the order of items within search tree