Fri Oct 19

Here is an implementation of a tree that stores values only at the interior branches; the leaves are empty.

Here is a link to lots of sample trees, with diagrams, built using these constructors.

You should instantiate the `Functor`

type class for `ITree`

, so we can do this:

```
ghci> fmap square t1
IBranch 9 (IBranch 16 ILeaf (IBranch 25 (IBranch 49 ILeaf ILeaf) ILeaf))
(IBranch 81 ILeaf ILeaf)
ghci> fmap show t1
IBranch "3" (IBranch "4" ILeaf (IBranch "5" (IBranch "7" ILeaf ILeaf) ILeaf))
(IBranch "9" ILeaf ILeaf)
```

That means using the `instance`

keyword and defining the function `fmap`

for the `ITree`

type. There are two examples of `Functor`

instantiations in the notes from 8 Oct.

```
instance Functor ITree where
fmap _ ILeaf = ILeaf
fmap f (IBranch v l r) = IBranch (f v) (fmap f l) (fmap f r)
```

Define the function `flipTree`

that swaps the left and right branches *throughout* the entire tree.

Below is a figure of a tree and its flipped counterpart:

This function converts a tree to a list.

The elements of the list should be ordered according to a **pre-order traversal.** That means for a branch, the element at that branch comes first, then the elements of the left sub-tree, then the right sub-tree.

So the pre-order traversal of `t1`

is:

```
ghci> preOrderList t1
[3,4,5,7,9]
ghci> preOrderList $ flipTree t1
[3,9,4,5,7]
```

A tree is **balanced** if at every branch, the difference in height between the left and right sub-trees is at most one. We’re going to determine whether a tree is balanced by returning a `Maybe Int`

. If the result is `Nothing`

then the tree is *not* balanced. A `Just`

result indicates it *is* balanced, with the specified height.

```
ghci> balancedHeight t1
Nothing
ghci> balancedHeight t7
Just 4
```

(You can see pictures of these sample trees, `t1`

and `t7`

, on this page.)

```
balancedHeight ILeaf = Just 0
balancedHeight (IBranch _ t1 t2) =
case balancedHeight t1 of
Nothing -> Nothing
Just n1 ->
case balancedHeight t2 of
Nothing -> Nothing
Just n2 ->
if abs (n1 - n2) > 1 then Nothing
else Just (1 + max n1 n2)
```

The way to approach `balancedHeight`

for a branch is to recursively compute the height of the left and right sub-trees. If either of those produces `Nothing`

, then we also return `Nothing`

. If those produce `Just n1`

for the left and `Just n2`

for the right, then we check the absolute value of the difference. If that difference is larger than 1, return `Nothing`

. Otherwise use `Just`

with the usual height formula: one more than the maximum height of left and right!

If we just want a Boolean to indicate balanced or not, we can compose with `isJust`

from the `Data.Maybe`

module:

Finally, we’d like to be able to take a list of elements and build a balanced tree. That means splitting the list in half (you can use `take`

and `drop`

).

Make sure that the list corresponds to a preorder traversal of the tree. That is, for any tree `t`

, we should have:

Also for any list `xs`

we should have:

```
balancedFromList [] = ILeaf
balancedFromList (x:xs) =
IBranch x (balancedFromList ys) (balancedFromList zs)
where
n = length xs `div` 2
ys = take n xs
zs = drop n xs
```

This is here just in case we need a `main`

function.