a Suppose that you have a full binary tree (any node has exactly two children or zero children). Prove by induction that a tree of this type with n leaves has exactly 2n 2 edges.

b (k-ary trees) Suppose that you have a tree such that any internal node has exactly k children, with k 2. What is the maximum number of nodes that such a tree can have, if its height is h? Prove your answer by mathematical induction on h.

c (k-ary trees) In such a tree of maximum number of nodes, what fraction of the nodes are leaves? Prove your answer by induction on h.