normally write the algorithm in pseudocodesuch as the following recursive procedureisin(value vtree tif isempty(treturn false elseif =root(treturn true elseif root(treturn isin(vleft( )else return isin(vright( )each recursion restricts the search to either the left or right subtree as appropriatereducing the search tree height by oneso the algorithm is guaranteed to terminate eventually in this casethe recursion can easily be transformed into while-loopisin(value vtree twhile (not isempty( )and ( !root( )if ( root(tt left(telse right(treturn not isempty(thereeach iteration of the while-loop restricts the search to either the left or right subtree as appropriate the only way to leave the loop is to have found the required valueor to only have an empty tree remainingso the procedure only needs to return whether or not the final tree is empty in practicewe often want to have more than simple true/false returned for exampleif we are searching for student idwe usually want pointer to the full record for that studentnot just confirmation that they exist in that casewe could store record pointer associated with the search key (idat each tree nodeand return the record pointer or null pointerrather than simple true or falsewhen an item is found or not found clearlythe basic tree structures we have been discussing can be elaborated in many different ways like this to form whatever data-structure is most appropriate for the problem at handbutas noted abovewe can abstract out such details for current purposes time complexity of insertion and search as alwaysit is important to understand the time complexity of our algorithms both item insertion and search in binary search tree will take at most as many comparisons as the height of the tree plus one at worstthis will be the number of nodes in the tree but how many comparisons are required on averageto answer this questionwe need to know the average height of binary search tree this can be calculated by taking all possible binary search trees of given size and measuring each of their heightswhich is by no means an