# Binary Trees

A great way to get more familiar with recursion is to work with binary trees. What are those? A binary tree is either empty or it is a node with a value and two subtrees. Those subtrees are either empty or a node with two subtrees. Etc. Here is a visual representation: Notice that every node has two subtrees. That is what makes this a binary tree. We can represent this data structure in Elm with a union type:

``````type Tree a
= Empty
| Node a (Tree a) (Tree a)
``````

So the tree in the image above would be represented like this:

``````exampleTree : Tree Int
exampleTree =
Node 4 (Node 1 Empty Empty) (Node 9 Empty Empty)
``````

To make it easier to work with these trees, we need to write a bunch of recursive functions!

## Member

Say we are curious if `9` is in `exampleTree`? As humans it is easy to see that it is, but how can we devise a system to make it easy for computers too? Well, say we maintain some invariants about our trees:

1. All values left of a `Node` must hold lower values.
2. All values right of a `Node` must hold higher values.

If we always follow these rules, we always know whether to go right or left from any node! So if we were looking for `9` we know it must be to the right of `4`. There it is! If we are looking for `7` we know it must be to the right of `4`. From there we know it must be left of `9`. Dead end. It is not in the tree. How do we write this as code though?

Well, we can always start with a `case`.

``````member : comparable -> Tree comparable -> Bool
member target tree =
case tree of
Empty ->
...

Node value left right ->
...
``````

If the `tree` is `Empty` we know we have not found the `target` value.

``````member : comparable -> Tree comparable -> Bool
member target tree =
case tree of
Empty ->
False

Node value left right ->
...
``````

We also know that if `target` is less than `value` it will be in the `left` subtree. Let’s try to check that.

``````member : comparable -> Tree comparable -> Bool
member target tree =
case tree of
Empty ->
False

Node value left right ->
if target < value then
...
else
...
``````

At this point we need to search the `left` subtree, so let’s pretend we are done with `member` and use it.

``````member : comparable -> Tree comparable -> Bool
member target tree =
case tree of
Empty ->
False

Node value left right ->
if target < value then
member target left
else
...
``````

We can do roughly the same thing if `target` is greater than `value`.

``````member : comparable -> Tree comparable -> Bool
member target tree =
case tree of
Empty ->
False

Node value left right ->
if target < value then
member target left
else if target > value then
member target right
else
...
``````

If the `target` is not less than `value` and it is not greater than `value`, it must be equal to `value`. That means we found our target!

``````member : comparable -> Tree comparable -> Bool
member target tree =
case tree of
Empty ->
False

Node value left right ->
if target < value then
member target left
else if target > value then
member target right
else
True
``````

There we go. A function that can find values in any tree.

Note: This means `member` is relatively cheap as you get more and more values. Say you have a binary tree that is ten levels deep. That means it holds about 1023 values. Checking for a value will be ten steps or fewer!

## Insert

Now we know how to check if values are in the tree, but how do we add new values? Remember the invariants we described for `member`? Lower values go left, higher values go right. If we want to insert `7` to `exampleTree`, we need to follow those rules: Now we want to turn that into code. The logic seems pretty similar to `member` so we will start with the same basic skeleton.

``````insert : comparable -> Tree comparable -> Tree comparable
insert target tree =
case tree of
Empty ->
...

Node value left right ->
if target < value then
...
else if target > value then
...
else
...
``````

If the `tree` is `Empty`, we want to insert our `target` value. The only thing we can really do here is say `Node target Empty Empty` to switch from a tree with no values to a tree with one value.

``````insert : comparable -> Tree comparable -> Tree comparable
insert target tree =
case tree of
Empty ->
Node target Empty Empty

Node value left right ->
if target < value then
...
else if target > value then
...
else
...
``````

Now if `target` is less than `value`, we know it needs to be inserted into the `left` subtree. We can pretend `insert` is done and use that.

``````insert : comparable -> Tree comparable -> Tree comparable
insert target tree =
case tree of
Empty ->
Node target Empty Empty

Node value left right ->
if target < value then
Node value (insert target left) right
else if target > value then
...
else
...
``````

Notice that we do not just call `insert` directly! We want to preserve the existing tree, just making a minor change to the `left` subtree. We can do the same thing if `target` is greater than `value`.

``````insert : comparable -> Tree comparable -> Tree comparable
insert target tree =
case tree of
Empty ->
Node target Empty Empty

Node value left right ->
if target < value then
Node value (insert target left) right
else if target > value then
Node value left (insert target right)
else
...
``````

Same idea but we `insert` on the `right` subtree. In the final case we know that `target == value` which means this value is already in the tree. That means we have nothing to insert.

``````insert : comparable -> Tree comparable -> Tree comparable
insert target tree =
case tree of
Empty ->
Node target Empty Empty

Node value left right ->
if target < value then
Node value (insert target left) right
else if target > value then
Node value left (insert target right)
else
tree
``````

Great, now our `insert` function will work exactly like the picture above if we evaluate `insert 7 exampleTree`. So if we wanted to make it easier to define binary trees, we could create a `fromList` function that just inserts a bunch of values:

``````fromList : List comparable -> Tree comparable
fromList list =
List.foldl insert Empty list

-- exampleTree = fromList [4,1,9]
``````

It looks like `fromList` may be quite expensive because calling `insert` creates a “totally new” binary tree. Thanks to immutability, it is actually pretty cheap!

Imagine we have a binary tree that is ten levels deep and it is totally full. It would hold about 1024 values. We are going to `insert` a value higher than all the others, so it should be added as the rightmost node. At the root, we know we need to `insert` on the right, so we can reuse the entire `left` subtree containing about 500 values. We need to go right again, so we can again reuse that `left` subtree which contains about 250 values. Etc.

In the end, we only need to replace the nodes that lead directly to the new entry in the tree. That means ten allocations, or about 1% of nodes. Sharing these massive subtrees between old and new trees does not cause any tricky bugs because all the values are immutable. That means someone from far away cannot sneakily mutate your tree!

Note: The `Dict` and `Set` libraries are actually balanced binary trees meaning that we do a bit of extra work to guarantee that the trees never get too lopsided. This is how we provide dictionaries that are fast and immutable.

## Depth and Map

Here are two more examples that may be helpful to look through. The `depth` function figures out how many levels are in a tree:

``````depth : Tree a -> Int
depth tree =
case tree of
Empty ->
0

Node v left right ->
1 + max (depth left) (depth right)
``````

And the `map` function transforms every value in the tree:

``````map : (a -> b) -> Tree a -> Tree b
map func tree =
case tree of
Empty ->
Empty

Node v left right ->
Node (func v) (map func left) (map func right)
``````

Both recursive functions were discovered using the “pretend you are done” strategy.

## Exercises

Exercise 1: Get the sum of all the values in a tree.

``````sum : Tree Int -> Int
sum tree =
...
``````

Exercise 2: Flatten a tree into a list.

``````flatten : Tree a -> List a
flatten tree =
...
``````

Try flattening it in different ways. Can you make it so the values are in-order in the resulting list? Can you use the `foo` and `fooHelp` technique to build up an in-order list without using `(++)`? Exercise 3: Write a fold function for trees. The fold function does not need to guarantee a particular order of traversal.

``````fold : (a -> b -> b) -> b -> Tree a -> b
Exercise 4: Use `fold` to define `member`, `sum`, and `flatten`.
Exercise 5: Try implementing `fold` with a bunch of different traversal strategies. Good ones to try are pre-order, in-order, and post-order.