4 Recursive Definitions and Structural Induction Consider the following recursive definition of binary trees: Base Case: A single vertex is a binary tree, and we call this vertex a root of that tree. Recursive Case: If v is a single vertex and To and T are two binary trees with roots respectively vo and vi, then the following is a 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 Ti 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 s.t. L(T) is a number of leaves in binary tree T 2. Give a recursive definition of function I s.t. I(T) is a number of intenal nodes in T. 3. Prove using structural induction that L(T) = 1(T) + 1