
\problemdata     
{S01-PS3-8}           
{structural induction, trees}              
{}              
{S01-PS3} 		
{S01 Karger}        	



\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$.
\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
  ever 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')$.

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}
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}
