Consider the following recursive definition of full binary trees: Base: A single vertex is a full binary tree, and we call this vertex a root of that tree. Recursive Rule: If v is a single vertex and To and T are two ful binary trees with roots respectively vo and v, then the following is a full binary tree with root v: A vertex v with a left outgoing edge from v to the root of To and a right outgoing edge from v to the root of T. Let FBT be the set of full binary trees defined by the above recursive definition. Call a vertex in a tree a leaf if it has no outgoing edges, and call it an internal node otherwise. 1. Give a recursive definition of function L : FBT N, where L(T) is a number of leaves in full binary tree T. 2. Give a recursive definition of function I : FBT N, where I(T) is a number of internal nodes in full binary tree T. 3. Prove using structural induction that L(T) = I(T) + 1 for every T E FBT. 6. In lectures, we considered the set B of binary trees defined recursively by: Base case: the trivial tree t = is in B; Recursive case: if T, T B then so is the tree T T given by T T = We can define recursive functions v: B N and e: B N which respectively count the number of vertices and the number of edges of a binary tree. For u we take: Base case: v(t) = 1; Recursive case: v(T * T) = v(T) + v(T) + 1. For e we take: Base case: e(t) = 0; Recursive case: e(T : T) = e(T) + e(T) +2.