searches the most important consequence of the structural property of binary search tree is its namesake search algorithm we can attempt to locate particular key in binary search tree by viewing it as decision tree (recall figure in this casethe question asked at each position is whether the desired key is less thanequal toor greater than the key stored at position pwhich we denote as keyif the answer is "less than,then the search continues in the left subtree if the answer is "equal,then the search terminates successfully if the answer is "greater than,then the search continues in the right subtree finallyif we reach an empty subtreethen the search terminates unsuccessfully (see figure ( (bfigure (aa successful search for key in binary search tree(ban unsuccessful search for key that terminates because there is no subtree to the left of the key we describe this approach in code fragment if key occurs in subtree rooted at pa call to treesearch(tpkresults in the position at which the key is foundin this casethe getitem map operation would return the associated value at that position in the event of an unsuccessful searchthe treesearch algorithm returns the final position explored on the search path (which we will later make use of when determining where to insert new item in search treealgorithm treesearch(tpk)if = key(then return {successful searchelse if key(and left(pis not none then return treesearch(tt left( ) {recur on left subtreeelse if key(and right(pis not none then return treesearch(tt right( ) {recur on right subtreereturn {unsuccessful searchcode fragment recursive search in binary search tree