1. (25 pts) Draw the binary search tree after removing the following values in sequence from the binary search tree in Figure 6.13 in Page 315 in the textbook. You must remove them using the delete method in Listing 6.5 in the textbook. crowed, man, jack, that Your final BST:

2. (25 pts) Build a MIN-Heap that would result from the following numbers in the given order. 15, 25, 10, 33, 55, 47, 82, 90, 18 Draw the final heap using two formats: a tree and an array like Figure 6.31 in Page 336 in the textbook. You must build the heap using the algorithm in Page 333 in the textbook. Your final MIN-Heap as a tree: Your final MIN-Heap as an array:

6.4 Binary Search Trees Overview of a Binary Search Tree In Section 6.1, we provided the following recursive definition of a binary search tree A set of nodes T is a binary search tree if either of the following is true: * T is empty If T is not empty, its root node has two subtrees, TL and TR, such that T, and T are binary search trees and the value in the root node of T is greater than all values in Ti and is less than all values in T Figure 6.13 shows a binary search tree that contains the words in lowercase from the nursery rhyme "The House That Jack Built." We can use the following algo- rithm to find an object in a binary search tree. FIGURE 6.13 Binary Search Tree Containing All of the Words from "The House That Jack Built la house rat jack milked that cow built dog is killed priest shorn tossed ma and cock crumpled forlorn in kept kissed maiden man morn shaven tattered this with all ate cat corn crowed farmer horn married the torn waked worried