$8)$ a$)$ Define binary search tree.

$$ b$)$ Why were we able to implement the binary search trees entirely by developing a class to represent binary search tree nodes?

$$ c$)$ What was the one problem we encountered with this implementation?

$$ d$)$ How can this problem be overcome?

$$

$9)$ Write two search methods for binary search trees, one implemented using linked nodes and the other an array.$$

$$

PART IV

$10)$ Given the following list of inputs: $45,54,89,32,23,58,65,76,88,55,42,12,38,34,57,79,90,66$

a$)$ Trace the development of the heap in abstract form that would evolve by inserting the inputs in the order that they are presented.

b$)$ Draw the final version of the array representation of this heap, i$.$e$.$ you need not show the array develop.

c$)$ What property of a heap led to the array being smaller than that of the binary search tree in problem $7$b$.$

d$)$ Why are heaps generally implemented with an array and not a linked structure?

$$

$11)$ Write an insert function for a heap class as well as all support functions that are called by your insert function.

$$

$12)$ Given the following list of values: $32,56,25,28,44,54,89$

Trace the steps of applying heapsort using both an array and a linked structure representation for the trace.