(a) All Lanky Trees of height h have the fewest nodes of any AVL tree of height h. How many nodes do they have? Express your answer using the Fibonacci function F().

The number of nodes in a Lanky Tree of height h is:

(b) How many leaves does a Lanky AVL Tree of height h have? Use everything youve learned so far to give us a concise description of this value.

(c) In any tree, a non-leaf node is referred to as an internal node. How many internal nodes does a Lanky AVL Tree of height h have? Be as concise as you can.

(d) Another way to count the number of Lanky Trees is to notice that the only difference between Lanky Trees is the order of the children at the internal nodes. Since the two children of an internal node have different heights in a Lanky Tree, swapping the order of the children produces a different Lanky Tree of the same height. How many Lanky Trees of height h are there as a function of I(h) defined above?

In this problem we will further explore the structure Lanky AVL trees. In each part, you should use the strategies you learned in problem 1 to create concise solutions. In some cases you'll start by writing down a recurrence, in others you'll observe something about the structure of the tree. We will be grading your scratch work, so please be as clear as you can in describing your derivations In this problem we will further explore the structure Lanky AVL trees. In each part, you should use the strategies you learned in problem 1 to create concise solutions. In some cases you'll start by writing down a recurrence, in others you'll observe something about the structure of the tree. We will be grading your scratch work, so please be as clear as you can in describing your derivations