Problem 1

Draw the following binary tree.

(24, -3), (12, -9), (15, -1), ((18, -4), (19, -5), (16, -6), (36, -9), (31, -10), (29, -13), (30, -4), (28, -7).

1- insert node (13, -14) and node (27, -23)

2- is the tree balanced?

3-Show the inOder, pre-Order and post-Order traversal of the tree.

4- delete node (18, -4)

5- delete node (29, -13)

6- If you had a reference to node (15, -1), what would be the Java code that would allow you to delete node (18, -4).

7- if you had a reference to node (31, -10) what would be the Java code that would allow your to delete node (29, -13).

Problem 2

Assume that you want to design a hashtable to store data of employees in a company that will not have more than 10000 workers at any time. The ID of each worker is his primary phone number in the form of 10 digit number (Area code-three digits carrier-4digits id).

a) How would you design your hash function for the index of most employees come from the same area code

b) What would be the size of the array that you would allocate? Explain

c) Give an example where two employees will have the same index. What would you do in this case? Why did you chose this solution.

d) would you chose a different algorithm, and allocate a different size if you know that the three digits following the area code are for the carrier (verizon, ) and most your employees have the same carrier? Explain.