1. BST: Using the definitions on p. 1177 of our textbook for depth of a tree node and height of a tree, consider the set of keys K = < 10, 4, 2, 8, 7 > and the different possible insertion orders for the keys in K. Based on the different possible insertion orders and their resulting Binary Search Trees, answer the following questions. (21 points)

a) What is the minimum height of a Binary Search Tree constructed from K? Show an insertion order for the keys in K that generates a Binary Search Tree of minimum height. Draw the corresponding Binary Search Tree.

b) Are there any other insertion orders (beyond what you found in (a) above) for the keys in K that produce a Binary Search Tree of minimum height? If so, provide one such sample insertion order and its accompanying Binary Search Tree.

c) What is the maximum height of a Binary Search Tree constructed from K? Show an insertion order for the keys in K that generates a Binary Search Tree of maximum height. Draw the corresponding Binary Search Tree.

2. For the set of keys given above in Problem 1, show the Binary Search Tree resulting from inserting the keys in the order given: K = < 10, 4, 2, 8, 7 >. Is it possible to color the resulting Binary Search Tree so that it becomes a red-black tree? Either prove that it is not possible or show a legal coloring that makes it a red-black tree. (15 points)

3. Chapter 13: For the set of keys given above in Problem 1, show the sequence of redblack trees that result after successively inserting the keys into an initially empty redblack tree in the order given: K = < 10, 4, 2, 8, 7 >. (Show one tree resulting from each insertion. State which case from the textbook applies. Assume that the root is always colored black.) (24 points)

4. Chapter 13: Starting from your answer to Problem 4, show the sequence of red-black trees that result after successively deleting the following sequence of keys (in this order) from the red-black tree: < 4, 8, 7 >. (Show one tree resulting from each deletion. State which case applies. Assume that the root is always colored black.) (20 points)