\problemdata     
{computation-8}           
{recursive definition of sets}              
{}              
{S02 in-class Week 5} 		
{S02 Meyer}        	

\newcommand{\ms}[1]{\mathop{\text{#1}}}
\providecommand{\ide}{\ms{id}}
\providecommand{\EF}{\ms{F18}}
\providecommand{\T}{\ms{ST}}
\providecommand{\leaves}{\ms{leaves}}
\providecommand{\nodes}{\ms{nodes}}
\providecommand{\makeb}{\ms{makeboth}}
\newcommand{\membern}{\ms{member}}
\newcommand{\makeleft}{\ms{makeleft}}
\newcommand{\makeright}{\ms{makeright}}
\newcommand{\deriv}{\frac{d}{dx}}
\renewcommand{\paren}[1]{\left(#1\right)}
\newcommand{\setl}{\mathbb{L}}
\newcommand{\setlone}{\mathbb{\ell}_1}
\newcommand{\setltwo}{\mathbb{\ell}_2}


\begin{problem}

\bparts

\ppart Give a recursive definition of the set of $\leaves$ of a Rooted
Binary Tree.

\solution{
Let $T, t_1, t_2$ be trees and let $\setl, \setlone, \setltwo$ represent their
respective sets of leaves.  We can then define the set of leaves of a
Rooted Binary Tree $T$ as follows:

\[
\begin{array}{llll}
 \setl &\eqdef& \set{T}&\text{if $|T|=1$ (the sole vertex of the tree is the
 only element of the set of leaves)}\\
\setl &\eqdef& \setlone&\text{if $T=\makeleft(t_1)$ or
 $T=\makeright(t_1)$}\\
\setl &\eqdef& \setlone \cup \setltwo& \text{if $T=\makeb(t_1, t_2)$}
\end{array}
\]
}


Full Binary Trees are the special case of RBT's in which only the
$\makeb$ constructor is used.  For example, Figure~\ref{fig:fullbintree}
shows an FBT with 13 nodes of which 7 are leaves:

\begin{figure}[h]
\begin{center}
\input{../figures/fbtree.pic}
\end{center}
\caption{A full binary tree.}
\label{fig:fullbintree}
\end{figure}


\ppart Prove by structural induction on the definition of FBT
that for all FBT's, $t$,
\[
2\card{\leaves(t)} = \card{\nodes(t)}+1.
\]
\solution{
Let $T, t_1, t_2$ be FBTs. Let $L, \ell_1, \ell_2$ represent their
\emph{number} of leaves and similarly let
$N, n_1, n_2$ represent their number of nodes. We want to prove that for
all FBTs we have: $2L~=~N +1$
\begin{description}
\item[Base case:] When $N=1$ (the tree has only one vertex), then $L=1$
(it has one leaf) and so the claim is true ($2=1+1$). 
\item[Inductive step:] Assume that the claim holds for trees $t_1$ and
$t_2$. We want to prove that $T=\makeb(t_1, t_2)$ also satisfies that
property. We have:
\[
\left.\begin{array}{lll}
2\cdot \ell_1 &=& n_1+1\\
2\cdot \ell_2 &=& n_2+1
\end{array}\right\} \implies
2\cdot (\ell_1 +\ell_2) ~=~ (n_1+n_2+1)+1\implies
2\cdot L ~=~ N+1
\]
So the claim holds for $T$ as well.
\end{description}
}



\eparts
\end{problem}
