## Part A: Analytical Problems (10 points)

Before getting started on the remaining problems, review the lecture and textbook materials on binary search trees and recursion. The following problems have to do with the BST in this diagram:

1. (5 parts): For this tree, give the (a) size, (b) depth of the node 31, (c) height, (d) length of the path from 11 to 49, and (e) list of all leaf nodes.

Solution: (a) 11 (b) 3 (c) 3 (d) 3 (e) 5, 10, 17, 31, 49

2. (2 parts) (a) Draw the result of inserting the keys 15, 7, 16, 12, & 13 into this tree; (b) assuming we can only insert integers, and no duplicates, into the original tree, what keys could possibly be inserted to the left of 31?

Solution: (a) Sideways printout:

```                49
43
31

19

17

16
15

13
12

11

10
8
7

6

5
4
```

(b) The only non-duplicate integers would have to be bigger than 19 and smaller than 31, so: 20, 21, ...., 29, 30.

3. (2 parts) (a) Draw the result of taking the tree in the diagram and deleting the root three times using the deletion algorithm from lecture (on 3/13); (b) suppose we do not wish to unbalance the tree by deleting from the same side each time, and we decide that we will alternately delete from the right, left, right, left, etc. (starting with the right); delete the root of the tree in the diagram 4 times using this new strategy and show the resulting tree.

Solution: (a)

```            49
43

31

10
8
6

5
4
```

(b)

```            49
43
31

8

6
5
4```

4. (2 parts) Let us call a tree "perfect" if it is a perfect triangle, i.e.,

Suppose H is the height of a perfect binary tree, and N the number of nodes; (a) express H as a function of N, and (b) N as a function of H.

Solution: Clearly there is some relationship between N and 2H and between H and log2(H); always a good idea to try a few examples in order to understand the details:

```  H      N      2^H      log2(N)
---    ---    -----    ---------
0      1       1        0
1      3       2        1.56
2      7       4        2.81
3     15       8        3.91
4     31      16        4.95
```
Thus, we have (a) H = floor(log2(N)) and (b) N = 2(H+1) - 1

, where floor(K) = (largest integer <= K) (same as "(int) K" in Java).

5. (2 parts): Suppose we are going to insert the letters A, B, C, and D, into an initially empty BST. If we insert them in order, we get a pathological tree which is really just a linked list (and whose worst case time to find a node is linear, i.e., O(N)). But there are many different worst cases! (a) List 5 more of the the possible worst cases (hint: there are 8 in all!). Now suppose we have the letters A, B, C, D, E, F, and G. We would like to have a perfect tree which has the shape of a perfect triangle: for example, we could insert in the order D, B, F, A, C, E, G. (b) List 5 more of the possible insertion orders that would give you a complete binary search tree.

Solution: (a) The worst cases occur if each time you pick an extreme value (largest or smallest) of those that remain:: ABCD, ABDC, ADCB, ADBC, DCBA,DCAB, DABC, DACB. (b) For a perfect tree, you must pick the median to be the root of the subtree each time, so any order which has D at the beginning, B before A and C, and F before E and G:

D...(any ordering of BF).... (any ordering of ACEG): DBFACEG, DBFGECA, DFBGECA, etc.

DB... (anything other than E or G) .... F....: DBACFEG, DBCFAEG, etc.

DF... (anything other than A or C) .... B....: DFGBAEC, DFEBCAE, etc.