produced when they are notbut that may have significant time cost if the procedure is called many times firstto find the smallest nodewe havesmallestnode(tree /preconditiont is non-empty binary search tree if isempty(left(treturn root(telse return smallestnode(left( ))which uses the fact thatby the definition of binary search treethe smallest node of is the left-most node it recursively looks in the left sub-tree till it reaches an empty treeat which point it can return the root the second sub-algorithm uses the same idearemovesmallestnode(tree /preconditiont is non-empty binary search tree if isempty(left(treturn right(telse return maketree(root( )removesmallestnode(left( ))right( )except that the remaining tree is returned rather than the smallest node these procedures are further examples of recursive algorithms in each casethe recursion is guaranteed to terminatebecause every recursive call involves smaller treewhich means that we will eventually find what we are looking for or reach an empty tree it is clear from the algorithm that the deletion of node requires the same number of steps as searching for nodeor inserting new nodei the average height of the binary search treeor (log nwhere is the total number of nodes on the tree checking whether binary tree is binary search tree building and using binary search trees as discussed above is usually enough howeveranother thing we sometimes need to do is check whether or not given binary tree is binary search treeso we need an algorithm to do that we know that an empty tree is (trivialbinary search treeand also that all nodes in the left sub-tree must be smaller than the root and themselves form binary search treeand all nodes in the right sub-tree must be greater than the root and themselves form binary search tree thus the obvious algorithm isisbst(tree tif isempty(treturn true else return allsmaller(left( ),root( )and isbst(left( )and allbigger(right( ),root( )and isbst(right( )