PLEASE READ THESE INSTRUCTIONS BEFORE YOU START THE PROBLEMS BELOW: 1. In the proofs to follow, you may use the recursive definitions above, as well as the recursive definitions for l(T) and i(T) given in the textbook, and your definitions for l(T) and i(T) in Problems 1 & 2 below. 2. DO NOT use the properties proved in the problems below in the proofs of other problems. YOU MUST DO EACH PROOF FROM SCRATCH using the recursive definitions for complete binary tree, balanced binary tree, h(T), n(T), l(T) and i(T). 3. Hint: the set of complete binary trees is a subset of the set of full binary trees.

Problem 4: (10 points) Draw the balanced binary trees formed by 0, 1 and 2 applications of the recursive step of the recursive definition above. For the 2nd application, draw 10 trees. (You dont have to draw the complete set of trees generated by the 2nd application.)

A balanced binary tree is a binary tree in which every leaf is either at level l or l-1 for some positive integer l. The set of balanced binary trees is defined recursively by: Basis step: A single vertex is a balanced binary tree. The tree with two vertices, namely a root and a left child (a leaf) is a balanced binary tree. The tree with two vertices, namely a root and a right child (a leaf) is a balanced binary tree. Recursive step: A balanced binary tree T= T1 T2 consists of a new root r together with edges connecting the r to each of the roots, r1 and r2, of two balanced binary trees, T1 (the left subtree) and T2 (the right subtree), respectively, where the leaves of T1 and T2 are at either level l or l-1 for some positive integer l.