Below is a binary search tree which holds the 26 letters of the alphabet. For the purposes of the ordering property of the binary search tree, assume that A

In order to search for the value at the root of the tree, we would have to examine 1 node and in order to search for a value in a leaf on the lowest level, we would examine 5 nodes.

On paper, fill out the values inside the nodes. Then, answer the following questions. Round your answers to two decimal places (4.333 -> 4.33, 4.555 -> 4.55 or 4.56, 4.5581 -> 4.56, 5.2 -> 5.2).

1. Assuming we are searching for a letter in the tree and that letter is equally likely to be any value from A to Z, what is the average number of nodes that would be examined?
2. We will define a vowel to be a letter from the set {A, E, I, O, U, Y}. Assume we choose a vowel at random (every vowel is equally likely to be selected) and search for it. How many nodes would be examined on average?
3. Now, assume we search for a vowel with probably 0.5 and for a consonant (a letter that is not a vowel) otherwise. Vowels are equally likely to be selected (with respect to each other) and so are consonants (again, with respect to each other). What is the average number of nodes that would be examined on a search?

O