# Planting Trees

## Planting Trees

Consider a binary tree with a type:

`data BinaryTree a = Leaf | Branch (BinaryTree a) a (BinaryTree a)`

Write the definition of the binary tree type, and then add the following functions:

```
-- Turn a binary tree of strings into a pretty-printed string
showStringTree :: BinaryTree String -> String
-- Add a new integer into a binary tree of integers
addElementToIntTree :: BinaryTree Int -> Int -> BinaryTree Int
-- Check to see if an int value exists in a binary tree of ints
doesIntExist :: BinaryTree Int -> Int -> Bool
```

### Hints

## Click to reveal

Try creating a helper function to turn a `BinaryTree Int`

into a `BinaryTree String`

to help you test and debug your functions.

## Click to reveal

You have several different options for how you can print your tree. Displaying it visually in the terminal as a tree may be pretty difficult right now. Instead, try thinking about other ways to print out the contents of the tree.

## Click to reveal

Don’t worry about keeping your binary tree balanced. For now, try to insert elements using the following rules:

- If the new element is smaller than the root of the tree, insert the element on the left
- If the new element is larger than the root of the tree, insert the element on the right
- If the new element is the same as the root of the tree, do nothing
- If the tree is empty, insert an element by creating a new root whose left and write sides are both empty leaves

## Click to reveal

Use this function to convert a tree of numbers into a tree of strings, so that you can easily print it out:

```
showTree :: BinaryTree Int -> BinaryTree String
Leaf = Leaf
showTree Branch l a r) = Branch (showTree l) (show a) (showTree r) showTree (
```

## Click to reveal

Try making `showString`

print out the elements in order. Here’s an example:

```
= addElementToIntTree (addElementToIntTree (addElementToIntTree Leaf 5) 0) 10
λ t
$ showTree t
λ showStringTree "0,5,10"
$ showTree (addElementToIntTree t 3)
λ showStringTree "0,3,5,10"
$ showTree (addElementToIntTree t 12)
λ showStringTree "0,5,10,12"
$ showTree (addElementToIntTree t 2)
λ showStringTree "0,2,5,10"
$ showTree (addElementToIntTree t 9)
λ showStringTree "0,5,9,10"
```

### Solution

## Click to reveal

The first part of this exercises asks us to find a way to print a binary tree containing strings. Since we don’t have a particular output format, let’s start with a naive printing function and refactor if we’re not happy with it:

```
showStringNaive :: BinaryTree String -> String
Leaf = ""
showStringNaive Branch l a r) =
showStringNaive (<> "," <> a <> "," <> rightStr
leftStr where
= showStringNaive l
leftStr = showStringNaive r rightStr
```

You’ll notice that the first thing we do is pattern match on the tree. Since a
`Leaf`

doesn’t have any value associated with it, we can just return an empty
string. To create a string for a `Branch`

, we needto include both the current
value in the branch, as well as the stringified versions of the left and right
subtrees.

Let’s load this up in `ghci`

and test it out:

```
$ Leaf
λ showStringNaive ""
$ Branch Leaf "a" Leaf
λ showStringNaive ",a,"
$ Branch (Branch Leaf "a" Leaf) "b" (Branch Leaf "c" Leaf)
λ showStringNaive ",a,,b,,c,"
```

Our elements are being printed out in order, which is what we want, but the
extra commas are pretty ugly. Let’s see if we can fix that. The first thing
we’ll do is to decouple traversing the tree from generating the output. Instead
of doing it all in one pass, we’ll add a helper function called
`binaryTreeToList`

that will traverse the tree and return a list with all of the
elements in the right order:

```
binaryTreeToList :: BinaryTree a -> [a]
Leaf = []
binaryTreeToList Branch l a r) =
binaryTreeToList (<> [a] <> binaryTreeToList r binaryTreeToList l
```

You can see that the logic here is more or less identical to the logic we used for putting the tree together, but we’re not trying to actually merge the strings together. This has the additional benefit that we can ignore the details about what kind of tree we’re dealing with, so we could use this for trees with data other than just strings.

Next, we need to combine the list of strings into a single string with commas
inbetween each element. There’s a function in from `Data.List`

in `Prelude`

that
can do this for us. It’s called `intercalate`

:

```
import Data.List (intercalate)
λ
:t intercalate
λ intercalate :: [a] -> [[a]] -> [a]
"," ["a","b","c"]
λ intercalate "a,b,c"
"," ["a"]
λ intercalate "a"
"," ["a","b"]
λ intercalate "a,b"
```

We can use this function make our program work as we’d hoped:

```
showStringTree :: BinaryTree String -> String
= intercalate "," . binaryTreeToList showStringTree
```

Let’s run this and see how it works:

```
$ Branch (Branch Leaf "a" Leaf) "b" (Branch Leaf "c" Leaf)
λ showStringTree "a,b,c"
```

Much better! This version of our function works just as we’d have
hoped. Unfortunately, we had to rely on a function that wasn’t covered in the
chapter to get there. Let’s address that by writing our own version of
`intercalate`

:

```
intercalate :: [a] -> [[a]] -> [a]
:y:ys) = x <> a <> intercalate a (y:ys)
intercalate a (x:_) = y
intercalate _ (y= [] intercalate _ []
```

You’ll notice that this function uses pattern matching a bit differently than many other examples you’ve seen. Normally, when we’re pattern matching on a list, we’re only pulling out a single element:

`:xs) (x`

In `intercalate`

we’re pattern matching on the first *two* elements of a
list. We only want to add a new element between pairs of elements- never before
or after a single element. Pattern matching on the first two elements allows us
to easily ensure that our list has two elements. In the second pattern, we only
have a single element list. In that case, we want to return it as is. Similarly,
in the last pattern, we have an empty list and so we can only return an empty
list. We can write this a bit more tersely by combining the last two patterns:

```
intercalate :: [a] -> [[a]] -> [a]
:y:ys) = x <> a <> intercalate a (y:ys)
intercalate a (x= concat rest intercalate _ rest
```

Let’s take one last look at all of this together:

```
showStringTree :: BinaryTree String -> String
= intercalate "," . binaryTreeToList
showStringTree
intercalate :: [a] -> [[a]] -> [a]
:y:ys) = x <> a <> intercalate a (y:ys)
intercalate a (x= concat rest
intercalate _ rest
binaryTreeToList :: BinaryTree a -> [a]
Leaf = []
binaryTreeToList Branch l a r) = binaryTreeToList l <> [a] <> binaryTreeToList r binaryTreeToList (
```

## Click to reveal

The next part of our exercises asks us to add an element to a tree of
`Int`

s. Just like the last part of this exercise, we have some flexibility here
to determine for ourselves exactly how we want to handle inserting a
value. Let’s go with a fairly simple approach. We won’t worry about keeping tree
balanced. The first element that we insert will become the root of our tree. Any
elements we insert that are numerically less than the root will go into the
left side of the tree, and any elements greater tan the root will go into the
right side of the tree. If an element already exists in the tree, we won’t
insert it again. Let’s take a look at the code:

```
addElementToIntTree :: BinaryTree Int -> Int -> BinaryTree Int
=
addElementToIntTree tree n case tree of
Leaf -> Branch Leaf n Leaf
Branch l a r
| n > a -> Branch l a (addElementToIntTree r n)
| n < a -> Branch (addElementToIntTree l n) a r
| otherwise -> Branch l a r
```

You’ll see that the code in this example maps pretty closely to our description
of the algorithm. We start by pattern matching on the tree. If it’s empty
(`Leaf`

) we create a new root node that contains our value, with empty left and
right subtrees (`Branch Leaf n Leaf`

). If we’ve got a branch, we compare it’s
value with our current value. If the value we’re insert is bigger, we
recursively insert our value into the right subtree. If it’s smaller, we
recursively insert our value into the left subtree. Otherwise, the values must
be the same and so we don’t need to do anything.

You’ll notice that we’re using a wildcard `otherwise`

guard in this example
instead of explicitly testing for equality. If we’d written the code with an
explicit equality test, it would have functioned the same way, but you might get
warnings about an incomplete pattern. Although we know that `n`

must always be
greater than, less than, or equal to `a`

, the compiler doesn’t know that and
assumes we might have missed a pattern.

Testing this solution isn’t entirely straightforward. In the last part of this exercise we built a program that would let us display trees full of strings, but now we’re working with trees full of numbers. Let’s write couple helper function to make it easier for us to view the results of inserting a new value:

```
showTree :: BinaryTree Int -> BinaryTree String
Leaf = Leaf
showTree Branch l a r) = Branch (showTree l) (show a) (showTree r) showTree (
```

This `showTree`

function will let us convert a tree containing numbers into a
`BinaryTree String`

that we can use with the `showStringTree`

function that we
wrote earlier. Let’s test it out:

```
. showTree $ Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)
λ showStringTree "1,2,3"
```

It looks like `showStringTree`

is working with a small example list. Let’s try
using `addElementToIntTree`

to add some numbers to a larger tree, then see if we
get the right output:

```
. showTree $ addElementToIntTree (addElementToIntTree (addElementToIntTree Leaf 2) 3) 1
λ showStringTree "1,2,3"
```

It works! It’s also a lot of typing! Let’s write another helpfer function- this time we’ll write one that lets us convert a list of numbers into a tree:

```
intTreeFromList :: [Int] -> BinaryTree Int
= foldl addElementToIntTree Leaf intTreeFromList
```

This function uses `foldl`

to add all of the elements from a list into the tree,
starting with an empty tree. As you can imagine, we could easily modify this
function to insert elements into an existing tree as well. We’re using `foldl`

here since our binary tree operations do not support infinite trees.

Let’s give this a shot to see if it works:

```
. showTree $ intTreeFromList [3,2,1]
λ showStringTree "1,2,3"
. showTree $ intTreeFromList [3,2,1]
λ showStringTree "1,2,3"
. showTree $ intTreeFromList [3,2,1]
λ showStringTree "1,2,3"
```

Our function works, and we can see that the order we insert elements
doesn’t matter, since `showStringTree`

will always print the elements in
order. It is worth keeping in mind that, since we are not rebalancing our tree
on insertion, adding elements that are already in order (or exactly in reverse)
results in an extremely unbalanced tree. This isn’t a problem per-se, just a
trade-off we made to keep the solution simple. As you get more experience with
Haskell you can continue to work on this exercise and try to build a version of
your insertion function that will rebalance itself.

## Click to reveal

The last question in this exercise asks us to write a function to find whether a particular value exists in a tree of numbers. This function ends up being very similar to our earlier insertion function:

```
doesIntExist :: BinaryTree Int -> Int -> Bool
Leaf _ = False
doesIntExist Branch l a r) n
doesIntExist (| n > a = doesIntExist r n
| n < a = doesIntExist l n
| otherwise = True
```

This algorithm relies on the tree being “well-formed”. That is to say, the tree
should follow the same structure that we used for `addElementToIntTree`

. Smaller
elements to the left, larger elements to the right. If the current element that
we’re looking at is an empyt `Leaf`

then we can be sure that the element doesn’t
exist in the tree. If we’re looking at a `Branch`

whose element matches what
we’re looking for, then we’ve found it. Otherwise, we can look at the left or
right subtree depending on whether the element we’re searching for is smaller or
larger than the element at the root of the current tree.