A proper d-ary tree, with d 1, is a tree where every node has either 0 or d children.

(a) Draw two proper ternary (d = 3) trees T1 and T2 with 8 internal nodes each and such that T1 has the maximum possible height and T2 has the minimum possible height. How many leaves do T1 and T2 have?

(b) Let T be a proper d-ary tree with n nodes, m of which are leaves, and of height h. Which one of the following relations can be true for any T?

i. m = (d 1)h + 1

ii. m = d(n m 1) 1

iii. m = (d 1)(n m) + 1

(c) Prove the relation guessed in (b).