search trees compare target to xx if target search the left subtree left subtree if target search the right subtree right subtree figure the structure of binary search tree is based on the search keys suppose we want to search for key value in the binary search tree from figure we begin by comparing the target to since the target is less than we move left the target is then compared to this time we move right since the target is larger than nextthe target is compared to resulting in move to the left finallywhen we examine the left child of node we find the target and report successful search the path taken to find key in the example tree is illustrated in figure (aby the dashed directed lines what if the target is not in the treefor examplesuppose we want to search for key we would repeat the same process used to find key as illustrated in figure (bthe difference is what happens when we reach node and compare it to the target if were in the the binary search treeit would have to be in the left subtree of node but you will notice node does not have left child if we continue in that directionwe will "falloff the tree thusreaching null child link during the search for target key indicates an unsuccessful search the binary search tree operations can be implemented iteratively or with the use of recursion we implement recursive functions for each operation and leave the iterative versions as exercises the bstsearch(helper methodprovided in lines - of listing recursively navigates binary search tree to find the node containing the target key the method has two base casesthe target is contained in the current node or null child link is encountered when base case is reachedthe method returns either reference to the node containing the key or noneback through all of the recursive calls the latter indicates the key was not ( ( null figure searching binary search tree(asuccessful search for and (bunsuccessful search for