Please answer the following questions. Thanks!

1. A BST is created (it is initially empty) where the key associated with the data in each node is an integer. Elements are added to the BST with these keys in this order: 5, 4, 8, 7, 6, 9, 3, 2, 1. (a) Draw the resulting BST. (b) What is the height of the tree?

2. Continuing, assume the keys of Exercise 5.6 are integers which are appened to a linked list of integers, i.e., the elements of the list will be 5, 4, 8, ..., 2, 1. Assume we always start from the head node when searching for an element. Complete this table which lists the number of comparisons that are made to locate each element in the list.

What is the average number of comparisons?

ElementNumber of Comparisons to Locate the Element 4