A full ternary tree is a rooted tree where each vertex has either 0 or 3 children. A full ternary tree can be generated using the following recursive definition: Basis step: A single vertex r is a full ternary tree. Recursive step: If T1, T2 and T3 are full, disjoint ternary trees, then there is a full ternary tree consisting of a root node r, with edges connecting to the roots of T1, T2, and T3.

(a) Give a recursive definition of the height H(T) of the full ternary tree.

(b) Give a recursive definition of the number of vertices N(T) in the full ternary tree.

(c) Prove by structural induction that N(T) 3^(H(T)+1) 1 for all full ternary trees.