        \problemdata       % Takes 5 *mandatory* arguments
        {number-search-trees}             % latex-friendly label for the prob.
        {str. induction}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut5-1, F00 PS, S01 PS3} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
\def\T{\cal N}

We define the family $\T$ of number search trees as follows:
\begin{enumerate}
\item
  Any single number $x$ is in $\T$.
\item If $T$ is in $\T$, and $x$ is a number greater than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``left'' from $x$ to $T$ is also in $\T$.
n\item If $T$ is in $\T$, and $x$ is a number smaller than any number
  in $T$, then the structure formed by pointing an arrow
  labelled ``right'' from $x$ to $T$ is also in $\T$.
\item If $T$ and $T'$ are in $\T$, and a number $x$ is larger than
  every number in $T$ but smaller than every number in $T'$, then the
  structure formed by attaching an arrow labelled ``left'' from $x$
  to $T$ and an arrow labelled ``right'' from $x$ to $T'$ is also in
  $\T$.
\end{enumerate}
In all cases above, the number $x$ is called the \emph{root} of the
tree that is formed.  Since the descriptions above are wordy, you may
wish to introduce some notation, like makeleft$(T,x)$ to denote the
thing built up according to the first recursive rule.  Likewise,
makeright$(x,T)$, makeboth$(T,x,T')$.

\problempart How many different number search trees with four nodes will be
in $\T$ if our domain consists of the numbers 1, 2, 3 and 4?  Give an
example of how one such tree might be constructed using the structural
definition.

\solution{Consider the number search tree with each number at the
root.  If 1 is at the root, 2, 3 and 4 must be to its right.  There
are five different number search trees that can be made with 2, 3 and
4, so there are three different trees that can be made with 1 at the
root.  If 2 is at the root, 1 must be to its left, and 3 and 4 to its
right.  Since there are two different number search trees that can be
made with 3 and 4, there are two different trees that can be made with
2 at the root.  When 3 is at the root, the case is very similar to 2,
and when 4 is at the root, the case is very similar to 1.  This means
there are 14 number search trees that can be made containing all of
the numbers 1, 2, 3 and 4.
\begin{center}
\begin{picture}(60,80)
\put(7,45){1}
\put(10,40){\circle*{3}} \put(10,40){\line(1,1){20}}
\put(27,65){2}
\put(30,60){\circle*{3}} \put(30,60){\line(1,-1){20}}
\put(47,45){4}
\put(50,40){\circle*{3}} \put(50,40){\line(-1,-2){10}}
\put(30,20){3}
\put(40,20){\circle*{3}}
%\put(10,40){\circle*{3}} %\put(10,40){\line(2,3){20}}
%\put(30,10){\circle*{3}}
\end{picture}\\
An example of a number search tree for the numbers 1, 2, 3 and 4.
\end{center}
}

Now consider the following recursive algorithm for checking whether a
certain number is present in a tree $T$.
\begin{tabbing}
else\=else\=else\=else\=\kill

Algorithm Member$(q,T)$\\
\\
\>Let $x$ be the root of tree $T$\\
\> {\bf if} $x=q$ {\bf then}\\
\> \> {\bf return} YES\\
\> {\bf else} \\
\> \> {\bf if} $q<x$ {\bf and} $x$ has a ``left'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else if} $q>x$ {\bf and} $x$ has a ``right'' arrow to tree $T'$ {\bf
  then}\\
\> \> \> {\bf return} Member$(q,T')$\\
\> \> {\bf else}\\
\> \> \> {\bf return} NO\\
\end{tabbing}

\problempart Prove that a call to member$(q,T)$ returns YES if and only if
$q$ is a number in the number search tree $T$.

\newcommand{\membern}{\hbox{member}}
\newcommand{\makeleft}{\hbox{makeleft}}
\newcommand{\makeright}{\hbox{makeright}}
\newcommand{\makeboth}{\hbox{makeboth}}

\solution{ We use structural induction. We use $x<T$ to mean
  $x<\mbox{all numbers in }T$, and define $x>T$ similarly. We get four
  cases, one for each production rule.
\begin{enumerate}
\item
For a single-node tree $T$ with root $x$, if $q\in T$, $q=x$ and 
$\hbox{member}(q,T)$ returns YES. If $q\notin T$, since there are no arrows
from $x$, the final else is taken and $\hbox{member}(q,T)$ returns NO.
\item
Fix $T$, and assume $\forall q$, $\hbox{member}(q,T)$ returns YES iff $q\in T$.
We need to show that $\forall q,\forall x>T$,
$\membern(q,\makeleft(T,x))$ returns YES iff $q\in\makeleft(T,x)$.
If $q\in\makeleft(T,x)$, $q=x$ or $q\in T$. If $q=x$,
$\membern(q,\makeleft(T,x))$ immediately returns YES. If $q\in T$, $q<x$
and since $x$ has a left arrow to $T$, $\membern(q,T)$ is returned,
which is YES by inductive assumption. If $q\notin\makeleft(T,x)$, then
$q\ne x$ and $q\notin T$, so either the final else is taken and NO
returned or $\membern(q,T)$ is returned, returning NO by inductive
assumption.
\item
Similar to 2.
\item
Fix $T$, $T'$ and assume $\forall q$, $\membern(q,T)$ returns YES iff
$q\in T$ and $\membern(q,T')$ returns YES iff $q\in T'$. We need to
show that $\forall q$, $\forall x\suchthat x>T\wedge x<T'$,
$\membern(q,\makeboth(T,x,T'))$ returns YES iff
$q\in\makeboth(T,x,T')$. If $q\in\makeboth(T,x,T')$, there are 3
cases. Case 1: $q=x$, so member returns YES. Case 2: $q\in T$, so
$q<x$, $x$ has a left arrow to $T$, and $\membern(q,T)$ is returned,
which is YES by inductive assumption. Case 3: $q\in T'$, by similar
reasoning YES is returned. If $q\notin\makeboth(T,x,T')$, then $q\ne
x$, $q\notin T$, and $q\notin T'$, so either NO is returned
immediately or $\membern(q,T)$ or $\membern(q,T')$ is returned, which
are NO by inductive assumption.
\end{enumerate}
}

\end{problem}
