\begin{patch}{BinarySearchTreeXmpPagePatch1}
\begin{paste}{BinarySearchTreeXmpPageFull1}{BinarySearchTreeXmpPageEmpty1}
\pastebutton{BinarySearchTreeXmpPageFull1}{\hidepaste}
\tab{5}\spadcommand{lv := [8,3,5,4,6,2,1,5,7]\bound{lv }}
\indentrel{3}\begin{verbatim}
   (1)  [8,3,5,4,6,2,1,5,7]
                             Type: List PositiveInteger
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty1}
\begin{paste}{BinarySearchTreeXmpPageEmpty1}{BinarySearchTreeXmpPagePatch1}
\pastebutton{BinarySearchTreeXmpPageEmpty1}{\showpaste}
\tab{5}\spadcommand{lv := [8,3,5,4,6,2,1,5,7]\bound{lv }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch2}
\begin{paste}{BinarySearchTreeXmpPageFull2}{BinarySearchTreeXmpPageEmpty2}
\pastebutton{BinarySearchTreeXmpPageFull2}{\hidepaste}
\tab{5}\spadcommand{t := binarySearchTree lv\free{lv }\bound{t }}
\indentrel{3}\begin{verbatim}
   (2)  [[[1,2,.],3,[4,5,[5,6,7]]],8,.]
                 Type: BinarySearchTree PositiveInteger
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty2}
\begin{paste}{BinarySearchTreeXmpPageEmpty2}{BinarySearchTreeXmpPagePatch2}
\pastebutton{BinarySearchTreeXmpPageEmpty2}{\showpaste}
\tab{5}\spadcommand{t := binarySearchTree lv\free{lv }\bound{t }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch3}
\begin{paste}{BinarySearchTreeXmpPageFull3}{BinarySearchTreeXmpPageEmpty3}
\pastebutton{BinarySearchTreeXmpPageFull3}{\hidepaste}
\tab{5}\spadcommand{emptybst := empty()$BSTREE(INT)\bound{e }}
\indentrel{3}\begin{verbatim}
   (3)  []
                         Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty3}
\begin{paste}{BinarySearchTreeXmpPageEmpty3}{BinarySearchTreeXmpPagePatch3}
\pastebutton{BinarySearchTreeXmpPageEmpty3}{\showpaste}
\tab{5}\spadcommand{emptybst := empty()$BSTREE(INT)\bound{e }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch4}
\begin{paste}{BinarySearchTreeXmpPageFull4}{BinarySearchTreeXmpPageEmpty4}
\pastebutton{BinarySearchTreeXmpPageFull4}{\hidepaste}
\tab{5}\spadcommand{t1 := insert!(8,emptybst)\free{e }\bound{t1 }}
\indentrel{3}\begin{verbatim}
   (4)  8
                         Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty4}
\begin{paste}{BinarySearchTreeXmpPageEmpty4}{BinarySearchTreeXmpPagePatch4}
\pastebutton{BinarySearchTreeXmpPageEmpty4}{\showpaste}
\tab{5}\spadcommand{t1 := insert!(8,emptybst)\free{e }\bound{t1 }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch5}
\begin{paste}{BinarySearchTreeXmpPageFull5}{BinarySearchTreeXmpPageEmpty5}
\pastebutton{BinarySearchTreeXmpPageFull5}{\hidepaste}
\tab{5}\spadcommand{insert!(3,t1)\free{t1 }}
\indentrel{3}\begin{verbatim}
   (5)  [3,8,.]
                         Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty5}
\begin{paste}{BinarySearchTreeXmpPageEmpty5}{BinarySearchTreeXmpPagePatch5}
\pastebutton{BinarySearchTreeXmpPageEmpty5}{\showpaste}
\tab{5}\spadcommand{insert!(3,t1)\free{t1 }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch6}
\begin{paste}{BinarySearchTreeXmpPageFull6}{BinarySearchTreeXmpPageEmpty6}
\pastebutton{BinarySearchTreeXmpPageFull6}{\hidepaste}
\tab{5}\spadcommand{leaves t\free{t }}
\indentrel{3}\begin{verbatim}
   (6)  [1,4,5,7]
                             Type: List PositiveInteger
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty6}
\begin{paste}{BinarySearchTreeXmpPageEmpty6}{BinarySearchTreeXmpPagePatch6}
\pastebutton{BinarySearchTreeXmpPageEmpty6}{\showpaste}
\tab{5}\spadcommand{leaves t\free{t }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch7}
\begin{paste}{BinarySearchTreeXmpPageFull7}{BinarySearchTreeXmpPageEmpty7}
\pastebutton{BinarySearchTreeXmpPageFull7}{\hidepaste}
\tab{5}\spadcommand{split(3,t)\free{t }}
\indentrel{3}\begin{verbatim}
   (7)
   [less= [1,2,.],greater= [[.,3,[4,5,[5,6,7]]],8,.]]
Type: Record(less: BinarySearchTree PositiveInteger,greater: BinarySearchTree PositiveInteger)
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty7}
\begin{paste}{BinarySearchTreeXmpPageEmpty7}{BinarySearchTreeXmpPagePatch7}
\pastebutton{BinarySearchTreeXmpPageEmpty7}{\showpaste}
\tab{5}\spadcommand{split(3,t)\free{t }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch8}
\begin{paste}{BinarySearchTreeXmpPageFull8}{BinarySearchTreeXmpPageEmpty8}
\pastebutton{BinarySearchTreeXmpPageFull8}{\hidepaste}
\tab{5}\spadcommand{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x }}
\indentrel{3}\begin{verbatim}
                                             Type: Void
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty8}
\begin{paste}{BinarySearchTreeXmpPageEmpty8}{BinarySearchTreeXmpPagePatch8}
\pastebutton{BinarySearchTreeXmpPageEmpty8}{\showpaste}
\tab{5}\spadcommand{insertRoot: (INT,BSTREE INT) -> BSTREE INT\bound{x }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch9}
\begin{paste}{BinarySearchTreeXmpPageFull9}{BinarySearchTreeXmpPageEmpty9}
\pastebutton{BinarySearchTreeXmpPageFull9}{\hidepaste}
\tab{5}\spadcommand{insertRoot(x, t) ==
    a := split(x, t)
    node(a.less, x, a.greater)
\bound{x1 }\free{x }}
\indentrel{3}\begin{verbatim}
                                             Type: Void
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty9}
\begin{paste}{BinarySearchTreeXmpPageEmpty9}{BinarySearchTreeXmpPagePatch9}
\pastebutton{BinarySearchTreeXmpPageEmpty9}{\showpaste}
\tab{5}\spadcommand{insertRoot(x, t) ==
    a := split(x, t)
    node(a.less, x, a.greater)
\bound{x1 }\free{x }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch10}
\begin{paste}{BinarySearchTreeXmpPageFull10}{BinarySearchTreeXmpPageEmpty10}
\pastebutton{BinarySearchTreeXmpPageFull10}{\hidepaste}
\tab{5}\spadcommand{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2 }\free{x1 e }}
\indentrel{3}\begin{verbatim}
                                             Type: Void
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty10}
\begin{paste}{BinarySearchTreeXmpPageEmpty10}{BinarySearchTreeXmpPagePatch10}
\pastebutton{BinarySearchTreeXmpPageEmpty10}{\showpaste}
\tab{5}\spadcommand{buildFromRoot ls == reduce(insertRoot,ls,emptybst)\bound{x2 }\free{x1 e }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch11}
\begin{paste}{BinarySearchTreeXmpPageFull11}{BinarySearchTreeXmpPageEmpty11}
\pastebutton{BinarySearchTreeXmpPageFull11}{\hidepaste}
\tab{5}\spadcommand{rt := buildFromRoot reverse lv\bound{rt }\free{lv x2 }}
\indentrel{3}\begin{verbatim}
   (11)  [[[1,2,.],3,[4,5,[5,6,7]]],8,.]
                         Type: BinarySearchTree Integer
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty11}
\begin{paste}{BinarySearchTreeXmpPageEmpty11}{BinarySearchTreeXmpPagePatch11}
\pastebutton{BinarySearchTreeXmpPageEmpty11}{\showpaste}
\tab{5}\spadcommand{rt := buildFromRoot reverse lv\bound{rt }\free{lv x2 }}
\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPagePatch12}
\begin{paste}{BinarySearchTreeXmpPageFull12}{BinarySearchTreeXmpPageEmpty12}
\pastebutton{BinarySearchTreeXmpPageFull12}{\hidepaste}
\tab{5}\spadcommand{(t = rt)@Boolean\free{rt t }}
\indentrel{3}\begin{verbatim}
   (12)  true
                                          Type: Boolean
\end{verbatim}
\indentrel{-3}\end{paste}\end{patch}

\begin{patch}{BinarySearchTreeXmpPageEmpty12}
\begin{paste}{BinarySearchTreeXmpPageEmpty12}{BinarySearchTreeXmpPagePatch12}
\pastebutton{BinarySearchTreeXmpPageEmpty12}{\showpaste}
\tab{5}\spadcommand{(t = rt)@Boolean\free{rt t }}
\end{paste}\end{patch}