**USE THE LANGUAGE SCHEME**

Deleting a value from a binary search tree can be tricky when you delete a node containing a value, the result must still be a binary search tree. There is an explanation below of the various cases you will need to consider. You will do this in parts, starting with the easier cases and then solving the general problem.

For each of these delete functions, the trees that are returned must maintain the binary search tree property explained below.

(a) Define a *Scheme* procedure, named bst-delete-min that takes a binary search tree, bst as a parameter and returns a binary search tree with the node that contains the minimum value removed from the tree that is, a binary search tree with the same values except for the minimum one. This procedure should not use bst-smallest or bst-delete.

(b) Define a Scheme procedure, named bst-delete-max that takes a binary search tree, bst as a parameter and returns a binary search tree with the node that contains the maximum value removed from the tree. This procedure should not use bst-largest or bst-delete.

(c) Finally, define a Scheme procedure, (bst-delete val bst) that takes a number val and a binary search tree bst as parameters and returns a binary search tree with the node that whose value is equal to val removed from the tree that is, the values in the resultant binary search tree will be the same as the original binary search tree with the exception of val; if val is in the original trees set it will not be in the resultant trees set, but the tree will have the same set if val was not in the original set.

Deleting nodes from trees Each of the above delete functions is tasked with removing one value (and its node) from the input binary search tree bst. Naturally, if bst has n nodes, the output tree has n 1 nodes (unless the value to be removed is not in the tree) and satisfies the binary search tree property (for every node n, the nodes in the left sub-tree of n hold values smaller than the value held in n and the nodes in the right-subtree of n hold values larger than the value held in n). There are number of cases that need to be handled separately: the node n may have no sub-trees, exactly one subtree, or two subtrees. (See Example 6.) The first two situations can be handled easily (Hint: how do these two relate to bst-delete-min and bst-delete-max?). The third case, illustrated below in Example 4, requires that you restructure the tree a bit to reattach the two orphaned subtrees of n in an appropriate way. One can either 1) replace the value at the deleted node with the largest value in the left subtree (or the smallest value in the right subtree) while removing the corresponding leaf node, or 2) promote the left subtree to the place where the node is to be deleted, and connect the right subtree to the node with the maximum value in the left subtree (you could also promote the right subtree and connect the left subtree to the rights minimum-valued node).