In this lab, we'll be using three kinds of trees: **binary trees**,
**binary search trees** and general or

You can use the following definitions from lecture to implement the various kinds of trees:

data BTree a = Tip | BNode a (BTree a) (BTree a) deriving Show
data Rose a = Branch a [Rose a] deriving Show

Note that you will in general need various list-processing functions (maps, etc.)
when dealing with `Rose`

trees, since lists are part of their definition.
Here are some sample trees you might want to use for testing, development and demo
(notice also the `leaf`

function, a little shorthand that makes entering
tree data easier):

leaf x = BNode x Tip Tip
samplebin = BNode 'A' (BNode 'B' (leaf 'C')
(leaf 'D'))
(BNode 'E' (BNode 'F' (leaf 'G') Tip)
(BNode 'H' (BNode 'I' Tip (leaf 'J'))
(leaf 'K')))
samplebst = BNode 37 (BNode 25 (leaf 12) (BNode 28 Tip (leaf 32)))
(BNode 51 (BNode 42 (leaf 39) (BNode 47 (leaf 43) (leaf 49)))
(BNode 69 Tip (BNode 81 (BNode 72 (leaf 71) Tip) Tip)))
sampler = Branch "Amarantha"
[ Branch "Bethesda" [Branch "Edna" []],
Branch "Callipygia"
[ Branch "Flegma" [Branch "Indicia"[],
Branch "Jaundice" [],
Branch "Kalahari" []
],
Branch "Ganache" []],
Branch "Depilitoria" [Branch "Hildegarde" [Branch "Ludmilla" [],
Branch "Miasma" []]]
]

**NOTE:** of the three sample trees given above, the `samplebin`

tree,
with letters, is **not** a search tree, just a plain binary tree ...
whereas the `samplebst`

tree, using numbers, **is** a (binary)
search tree.

You can see pictures of the two binary trees below; the general or rose tree
`sampler`

is a family tree from
a lab exercise
in my *Data Structures* course (the names are supposed to be those of the princesses
of some far-away fantasy realm).

- Write the
`postord`

function we left out in lecture; it should return the postorder traversal of a`BTree`

, where the left and right sub-trees are traversed first, and the node value is "visited" last.`samplebin`

binary tree from above, you should have:Trees> postord samplebin "CDBGFJIKHEA"

- Write two functions (discussed in lecture!) to find the minimum and maximum
values from a binary search tree; call them
`mint`

and`maxt`

. These functions should use the`Maybe`

type in the result in order to allow for empty trees (which don't have a minimum or maximum value).Trees> mint samplebst Just 12 Trees> maxt samplebst Just 81

- Write a function called
`path`

which will return a list of "directions" to take to get to a particular value in a*binary search tree.*For the directions you may use the following data type:

Your function should accept a value that might be an item in a binary search tree, plus a tree itself, and return a path as a list ofdata Dir = L | R deriving Show

`Dir`

values. You may use either an error message or the`Maybe`

type to handle missing values.path :: Ord a => a -> BTree a -> [Dir]

**OR***(just one!)*path :: Ord a => a -> BTree a -> Maybe [Dir]

If you try the

`Maybe`

-fied version, you may want to use the following utility function to "push" a function "inside" a`Maybe`

value (technically, this is really just the`fmap`

function from the`Maybe`

instance of the`Functor`

type class, but you needn't worry too much about that):push :: (a -> b) -> Maybe a -> Maybe b push f Nothing = Nothing push f (Just x) = Just (f x)

- Write each of the following functions for general trees (a.k.a. rose trees):
`rsize :: Rose a -> Integer`

, to count the number of node values in a rose tree;`rheight :: Rose a -> Integer`

, to measure the height, or longest path from the root to a child (count the height of a leaf as one);`rmap :: (a -> b) -> Rose a -> Rose b`

, to map a function across the node values in a rose tree`rzip :: Rose a -> Rose b -> Rose (a,b)`

, to zip together two rose trees into a tree of pairs; just as with the usual`zip`

function on lists, you should trim the results to the minimum available structure between the two input trees.`rmirror :: Rose a -> Rose a`

, to return the "symmetric opposite" of a rose tree, as if it were mirrored down the middle.