# Tute Exercises Week 12

## Trees

In the lecture, we defined generic trees as

data Tree a = Leaf
| Node a (Tree a) (Tree a)
deriving (Show)

We call trees like `Tree`, which store elements in their nodes, *augmented
trees*.
As discussed in the lecture, a *ordered binary tree* is an augmented tree where

- for any given node, if the node stores a value
*x,* then all
the integers stored in nodes of the left subtree must be
smaller than *x.*
- for any given node, if the node stores a value
*x,* then all
the integers stored in nodes of the right subtree must be
greater than *x.*

(note that we assume here, for simplicity reasons, that the tree
holds no duplicate items)
We defined the following functions in the lecture:

insertTree:: Ord a => a -> Tree a -> Tree a
insertTree x Leaf = Node x Leaf Leaf
insertTree x (Node y tree1 tree2)
| x < y = Node y (insertTree x tree1) tree2
| x == y = error "insertTree: element already in tree!\n"
| otherwise = Node y tree1 (insertTree x tree2)

Implement a function `deleteFromTree:: Ord a => a -> Tree a -> Tree a` which,
given an ordered tree and an item, searches for the item and if found,
deletes it from the tree. The resulting tree does not have to be
ordered. Note that there is more than one correct way to delete an
item from a tree. For example, deleting `5` in tree
Node 5
/ \
Node 2 Node 6
/ \ / \
Leaf Leaf Leaf Leaf

can result in either
Node 2
/ \
Leaf Node 6
/ \
Leaf Leaf

or
Node 6
/ \
Node 2 Leaf
/ \
Leaf Leaf

That is, if you delete a Node value, you can either rotate the remaining
elements to the left or to the right.

#### Data Types and Equivalence

The following is an alternative definition of an augmented tree
- it stores values in the node and the leaves:
data Tree1 a = Leaf1 a
| Node1 a (Tree1 a) (Tree1 a)
deriving (Show)

Two data types `T1` and `T2` are equivalent if we can write
functions `toT2:: T1 -> T2` and `toT1:: T2 -> T1`
such that `toT2 (toT1 x) = x` and `toT1 (toT1 y) =
y` for all `x :: T2` and `y :: T1` (or in more
mathematical terms, the functions are *bijective*)

In particular, if two types differ only in the names of the data constructors,
the two types are equivalent. In case of `Tree` and `Tree1`,
`Leaf1` has one argument, whereas `Leaf` has none. Are they
still equivalent? Why is the type `Tree a` not equivalent to
`[a]`?