Please answer following questions.

1. Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the order given? Use the algorithm discussed in class and textbook; namely search the binary search tree for the new entry, and insert the new entry at the position it would have been found.

A, B, W, J, N, T, E

2. Same as question 1, but with the following values:

B, T, E, A, N, W, J

3. What is the maximum number of nodes in a binary search tree of height 3? 4? h?

4. In which order could you insert these values into an empty binary search tree in order to create a binary search tree with height 3? A, B, W, J, N, T, E.

5. Consider the binary search tree below. If you start with this binary search tree, what does it look like after you insert the nodes 80, 65, 75, 45, 35, and 25 in that order?

0060 0020 0070 0010 0040 0030) 0050