listing searching for target key in binary search tree class bstmap determines if the map contains the given key def __contains__selfkey )return self _bstsearchself _rootkey is not none returns the value associated with the key def valueofselfkey )node self _bstsearchself _rootkey assert node is not none"invalid map key return node value helper method that recursively searches the tree for target key def _bstsearchselfsubtreetarget )if subtree is none base case return none elif target subtree key target is left of the subtree root return self _bstsearchsubtree left elif target subtree key target is right of the subtree root return self _bstsearchsubtree right else base case return subtree found in the tree the recursive call is made by passing the link to either the left or right subtree depending on the relationship between the target and the key in the current node you may be wondering why we return reference to the node and not just boolean value to indicate the success or failure of the search this allows us to use the same helper method to implement both the contains and valueof(methods of the map class both call the recursive helper method to locate the node containing the target key in doing sothe root node reference has to be passed to the helper to initiate the recursion the value returned from bstsearch(can be evaluated to determine if the key was found in the tree and the appropriate action can be taken for the corresponding map adt operation binary search tree can be emptyas indicated by null root referenceso we must ensure any operation performed on the tree also works when the tree is empty in the bstsearch(methodthis is handled by the first base case on the first call to the method min and max values another operation similar to search that can be performed on binary search tree is finding the minimum or maximum key values given the definition of the binary search treewe know the minimum value is either in the root or in node to its left but how do we know if the root is the smallest value and not somewhere in its left subtreewe could compare the root to its left childbut if you think about itthere is no need to compare the individual keys the reason has to do