--------------------------------------------------------------------- Important: Remember that in a proper binary tree, the number of leaves is one more than the number of internal nodes. (We already proved this!) ---------------------------------------------------------------------Base case:Tree with 1 node. i=0, E=0, I=0; 0=0+2*0.Inductive step:If for any proper tree with 1<=r<=k internal nodes _________________, then for any proper tree with k+1 internal nodes _________________.Proof:Consider a proper binary tree T with k+1 internal nodes. nodes. Since T is proper, it must have two subtrees, T1 and T2. Suppose T1 has i internal nodes; then T2 must have _____________ internal nodes. Note that by a previously proven property of proper binary trees (above), T1 must have __________ leaves and T2 must have ____________ leaves.Path lengths of the subtreesIf I1 and E1 are the internal and external path lengths for T1, and I2 and E2 are the internal and external path lengths for T2, then by the inductive hypothesis, E1 = _________________ (1) and E2 = _________________ (2)The external path length of TThe external path length of T is the sum of the external path lengths of T1 and T2 plus the number of leaves in T1 and T2, since each leaf is one level deeper in T than in the subtree. So E = __________________________ which simplifies to E = E1 + E2 + k + 2 (3)The internal path length of TThe internal path length of T is the sum of the internal path lengths of T1 and T2 plus the number of internal nodes in T1 and T2, since each node is one level deeper in T than in the subtree. So I = ____________________ (4)Putting it all togetherUsing equations (1) and (2) to substitute for E1 and E2 in equation (3) gives E = ________________________________________ which simplifies to E = ____________________ (5) Rearranging (4), we see that (I1 + I2) = _________________ Using this to substitute for I1 + I2 in (5) gives E = ___________________________ which simplifies to E = ___________________________ Voila!