# Introduction

Binary trees have internal structure; for any given node, all elements to the left are less than the current value, and all elements to the right are greater than the current value.

For instance:

```
5
/--+--\
3 6
/-+-\
1 2
```

Lets build a binary tree in Haskell.

# Type Definition

A lot of the power of Haskell comes from it's type system. New types can be defined in terms of existing types (a type constructor), as aliases for existing types (AuthorName :: String), or as original items (EmptyTree).

Lets define a tree using a type constructor (a type that works on another
type). It doesn't make much sense to just have a 'tree', it's a tree of
'something', like a tree of `Int`

or `String`

. The only constraint is a way to
compare the elements that our tree will be made of. Without some way to compare
elements, we won't be able to decide whether to place an element in the left or
right side when we're inserting elements.

Our `BinaryTree`

may either be an `EmptyTree`

or a `Node`

. A `Node`

is composed
of a value, the 'something' we're making the tree of, and a left and right
side, which are also trees.

```
module BinaryTree where
data Tree a = EmptyTree
| Node a (Tree a) (Tree a) deriving (Read, Eq)
```

The snippet `deriving (Read, Eq)`

tells Haskell that our `Tree`

can be compared
to other trees and can be parsed from a string representation. We could write
out a tree to a file, and Haskell would know how to read it back into a tree.

# Tree operations

What can we do with our new tree? Add elements, remove elements, check if an
element is a member, and get height. Each of these functions can be defined
recursively with pattern matching using our new types. We'll use `EmptyTree`

as
our base case.

The type definitions for insert and elem require that the elements of our tree are orderable. To tell if the element we're looking for is what we've found, we have to have a way to compare items. This may seem strange compared to other languages where most types are comparable - you might draw an analogy with a complex class in Python and Java. Is this object less than another? What does that mean?

- Insert takes an 'orderable something', an existing tree, and produces a new
tree. We also require that the element we're inserting and the tree's
elements have the same type. This makes sense, and keeps us from trying to
insert a
`String`

into a tree of`Int`

, etc.

```
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = Node x EmptyTree EmptyTree
treeInsert x (Node a left right)
| x == a = Node x left right
| x < a = Node a (treeInsert x left) right
| x > a = Node a left (treeInsert x right)
```

- Elem also takes an 'orderable something' to look for, an existing tree and produces a boolean.

```
treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
| x == a = True
| x < a = treeElem x left
| x > a = treeElem x right
```

- Height only requires a tree and produces an
`Int`

. If you could manually construct a tree of elements that aren't orderable (meaning you couldn't use insert), we can still determine the height of the tree.

```
treeHeight :: Tree a -> Int
treeHeight EmptyTree = 0
treeHeight (Node a left right) = maximum [1, lh, rh]
where lh = 1 + treeHeight left
rh = 1 + treeHeight right
```

# Printing

Haskell can print our trees using the structure we defined in the type, but it
doesn't look great. We can do the work of `deriving (Show)`

ourselves and
produce prettier output.

The type definition states that for a tree to be converted to a string, the elements of the tree must also be convertable to string. We could show the structure of the tree without this requirement, but we wouldn't be able to represent the values.

```
haskell> Node 5 (Node 3 EmptyTree (Node 4 EmptyTree EmptyTree)) EmptyTree
3
4
5
```

```
instance (Show a) => Show (Tree a) where
show EmptyTree = ""
show tree = show' tree 0 (widestElement tree + 1)
```

`show'`

is a helper function that has the extra context we need to pretty
print - depth and padding. Each subtree is printed further to the right.
widestElement tells us how much to pad elements so they align.

```
show' :: (Show a) => Tree a -> Int -> Int -> String
show' EmptyTree _ _ = " "
show' (Node a left right) depth width =
leftside ++ "\n" ++ center ++ rightside
where center = replicate depth ' ' ++ show a
leftside = show' left (depth + width) width
rightside = show' right (depth + width) width
widestElement :: (Show a) => Tree a -> Int
widestElement EmptyTree = 0
widestElement (Node center left right) = maximum [l, r, c]
where l = widestElement left
r = widestElement right
c = length $ show center
```

# Building Trees

Manually defining trees can be a bit of work, so let's define some helper functions.

`makeTree`

takes a list of elements and inserts them into an EmptyTree

```
makeTree :: (Ord a) => [a] -> Tree a
makeTree = foldr treeInsert EmptyTree . reverse
```

```
haskell> makeTree [14,3,16,37,250,21]
3
14
16
21
37
250
```

`randomTree`

produces a random tree of numbers with the specified number of elements

```
randomTree :: Int -> IO (Tree Int)
randomTree n = do
numbers <- randomList n
return $ makeTree numbers
import System.Random (randomRIO)
randomList :: Int -> IO([Int])
randomList 0 = return []
randomList n = do
r <- randomRIO (1,99)
rs <- randomList (n-1)
return (r:rs)
```

```
haskell> randomTree 5
16
57
73
75
87
```

# Summary

Haskell's type system makes defining types straight forward. The type declarations for the functions we define force us to answer interesting questions about how we expect things to behave, and the constraints required.

```
haskell> randomTree 20
2
3
6
8
12
14
20
22
23
34
37
43
70
73
84
86
92
96
99
```