- improving the time and/or space complexity of an algorithm, and
- dealing with problems for which a recursively defined algorithm cannot readily be found.

The file binTrees.sml has
the beginning of a realisation of a polymorphic abstract datatype
(ADT) `'a bTree` for binary trees, specified on slides 6.19 to 6.24. The file trees.sml has sample
binary trees for your tests and the examples below. Add the following
functions to that ADT, but declare it as a *non-abstract*
datatype, just to ease the testing:

- The function
`preorder`returns the preorder walk, as a list, of a binary tree.

**Example:**`preorder smallIntTree = [1,2,5,7,3,6,10,13]`

**Requirements:**Do*not*use any help functions. Is your function tail-recursive? Why / Why not? - The function
`preorder'`has the same specification as`preorder`.

**Requirements:**Use exactly*one*help function, which must be obtained by introducing an accumulator. (This technique is also known as performing a*descending generalisation*.) Is your help function tail-recursive? Why / Why not? - The function
`preorders`takes a*list*of binary trees as an argument and returns the concatenation of the preorder walks of the trees in that list. (This specification was obtained by performing a*tupling generalisation*.)

**Example:**`preorders [smallIntTree,anotherSmallIntTree] = [1,2,5,7,3,6,10,13,2,1,7,5,13,3,6,10]`

**Requirements:**Do*not*use any help functions. Each clause must have*at most one*recursive call. Is your function tail-recursive? Why / Why not? - The function
`preorder''`has the same specification as`preorder`.

**Requirement:**Use`preorders`as help function. - Give recurrences for the
*average*-case running times*T*,*T'*, and*T''*of your`preorder`,`preorder'`, and`preorder''`functions, respectively. Make explicit the costs of every part of their*dividing*,*conquering*(recurring), and*combining*parts, and relate these costs to the relevant parts of these functions. State any assumptions you make. - Derive tight asymptotic bounds Θ(...) for
*T*,*T'*, and*T''*, using the Master Theorem where applicable; otherwise, first state why it is not applicable and then use any other relevant method or theorem. In any case, always show*all*the details of your reasoning. Discuss the results.

- SML funktionerna för frågorna 1-4 ovan, i en *.sml textfil, körbar under Moscow ML version 2.01 (det som inte är kod ska vara bortkommenterat), och dokumenteras, på engelska, enligt kursens kodkonventionerna.
- Svar, på engelska, på frågorna 5-6 ovan, i en *.txt eller *.pdf eller *.html fil.