\problemdata                                                             
        {Height of Binary Trees} % latex-friendly label for the prob.
        {Structural Induction} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Quiz 1, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Recall from class the following recursive definition of the set~$F$
    of \emph{binary trees:}
    
    \begin{enumerate}\itemsep 0\baselineskip
    \item A single node is in~$F$.
    \item $\forall t \in F (\mbox{makeleft}(t) \in F)$ 
    \item $\forall t \in F (\mbox{makeright}(t) \in F)$     
    \item $\forall t,t' \in F (\mbox{makeboth}(t,t') \in F)$
    \end{enumerate}

Recall also the definition of the number of nodes $n$ in a tree:
\begin{enumerate}\itemsep 0\baselineskip
\item A single node tree has one node
\item $n(\mbox{makeleft}(t)) = 1+n(t)$
\item $n(\mbox{makeright}(t)) = 1+n(t)$
\item $n(\mbox{makeboth}(t,t')) = 1+n(t)+n(t')$
\end{enumerate}

Consider also the following recursive definition of the height $h$ of a
binary tree:
\begin{enumerate}\itemsep 0\baselineskip
\item The height of a single node is 0
\item $h(\mbox{makeleft}(t)) = 1+h(t)$
\item $h(\mbox{makeright}(t)) = 1+h(t)$
\item $h(\mbox{makeboth}(t,t')) = 1+\max(h(t),h(t'))$
\end{enumerate}

Prove that a binary tree of height $h$ has at most $2^{(h+1)}-1$ nodes. 

\solution{
Base Case: For any tree of height 0, there is at most 1 node. Therefore $2^{(0+1)}-1 = 1 \geq 1$\\
Inductive Step:\\
\begin{itemize}
\item Case 1: $\mbox{makeleft}(t)$\\
\begin{eqnarray*}
n(\mbox{makeleft}(t)) &=& n(t) + 1\\
&\leq& (2^{h(t)+1} - 1) + 1\\
&\leq& 2 \cdot (2^{h(t)+1} - 1) + 1\\
&=& 2 \cdot (2^{h(t)+1}) - 2 + 1\\
&=& 2^{h(\mbox{makeleft}(t)) + 1} - 2 + 1\\
&=& 2^{h(\mbox{makeleft}(t)) + 1} - 1
\end{eqnarray*}

since $h(t) + 1 = h(\mbox{makeleft}(t))$\\.
Thus $n\mbox{makeleft}(t) \leq 2^{h(\mbox{makeleft}(t))+1} - 1$.

\item Case 2: $\mbox{makeright}(t)$\\
Similar to Case 1.

\item Case 3: $\mbox{makeboth}(t,t')$\\
\begin{eqnarray*}
n(\mbox{makeboth}(t,t')) &=& n(t) + n(t') + 1\\
&\leq& (2^{h(t) +1} - 1) + (2^{h(t') + 1} - 1) + 1\\
&\leq& 2 \cdot (2^{max(h(t), h(t')) +1} - 1) + 1\\
&\leq& 2 \cdot ( 2^{h(\mbox{makeboth}(t,t'))} - 1) + 1\\
&=& 2^{h(\mbox{makeboth}(t,t')) + 1} - 2 + 1\\
&=& 2^{h(\mbox{makeboth}(t,t')) + 1} - 1
\end{eqnarray*}

since $max(h(t), h(t')) + 1 = h(\mbox{makeboth}(t,t'))$\\.
Thus $n(\mbox{makeboth}(t,t')) \leq 2^{h(\mbox{makeboth}(t,t'))+1} - 1$.
\end{itemize}

Points were taken off for simply relying on one's intuitive idea of a binary
tree without working from the makeleft, makeright, makeboth definitions, since
the definitions were explicitly given in the problem. Some students
failed to realize that getting a new tree from makeboth involves two 
(possibly distinct) trees. Also, some students reversed the logic of
the induction; i.e., wrote down the inequality they were trying to
prove and manipulated it into the inductive assumption; the direction
of steps should go from the inductive assumption to the statement
being proved.
}

\end{problem}
                                 