# CS 254 Lab 6: The Botany Lab (trees!)

In this lab, we'll be using three kinds of trees: binary trees, binary search trees and general or rose trees. Recall from lecture that a binary search tree is structurally the same as a binary tree (and we'll use empty tips for each of them), but with the extra ordering property that every node value to the left of a given node is less than the value in that node, and vice versa every node value to the right is greater.

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).

## The exercises

1. 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.

For example, using the `samplebin` binary tree from above, you should have:
```Trees> postord samplebin "CDBGFJIKHEA" ```
2. 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 ```
3. 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:
```data Dir = L | R deriving Show ```
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 of `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) ```
4. Write each of the following functions for general trees (a.k.a. rose trees):

1. `rsize :: Rose a -> Integer`, to count the number of node values in a rose tree;
2. `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);
3. `rmap :: (a -> b) -> Rose a -> Rose b`, to map a function across the node values in a rose tree
4. `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.
5. `rmirror :: Rose a -> Rose a`, to return the "symmetric opposite" of a rose tree, as if it were mirrored down the middle.