Problem 8 and 9

In the language java

PART III 7) Given the following list of values: 45, 54, 89, 32, 23, 58, 65, 76, 88, 55, 42, 12, 38, 34, 57, 79,90, 66 a) Draw the binary search tree that would evolve by inserting the values into the tree in the order in which they are presented b) Draw the array representation of this binary scarch tree. You may use notation as long as you label the array cells c) In what order would you insert the valucs so as to get a complete binary search tree? d) In what order would you insert the values so as to get a linked list that uses left references only? Right references only?c c) How many elements would be needed for each of the binary trees described in part d if implemented as array s? 1 Why are binary scarch tree more often implemented using linked structures rather than arrays? 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 scarch methods for binary search trees, one implemented using linked nodes and the other an array