Problem 1 [4 points]

Consider an AVL tree whose root has a height of 5. What is the maximum difference between the depths of any two leaves in this tree. Briefly justify your answer.

Problem 2 [8 points]

Starting with an empty AVL tree, insert the following keys in the order given: 0, 17, 6, 4, 5, 10, 15, 13, 12, 11. Show the AVL tree after each insertion. If the insertion requires a rotation operation to restore the balance, clearly indicate the specific type of rotation required. Show the result after the rotation operation required has been applied. After you have finished inserting all ten elements, you are required to give the height of the final AVL tree that resulted from this particular sequence of insertions.

Problem 3 [8 points]

Perform the same steps as in the last problem, but use a Red-Black tree instead.