#4 Red-Black Tree Height (6 pts)

(a) (4 pts) What is the largest possible number of internal nodes (those with keys) in a red-black tree with black height k? What is the height of the corresponding 2-4 tree? Prove your claims.

(b) (2 pts) What is the smallest possible number of internal nodes (those with keys) in a red-black tree with black height k? What is the height of the corresponding 2-4 tree? Prove your claims (you may use Lemma 13.1).