# Grow a Tree

In Computer Science, trees grow upside-down. The unique *root*

is at the top, and the *leaves* are at the bottom.

The binary tree data type is often used for storing data in a sorted order, to allow efficient searching — for example, a telephone directory.

We are going to define a Haskell data type for trees, storing integer values.

```
data Tree = Leaf | Node Int Tree Tree deriving Show
```

A `Tree`

value might be either a `Leaf`

or a `Node`

.
Note that this is a *recursive* data type, since a `Node`

stores an
`Int`

payload and has branches to two subtrees (sometimes called children).

Here is the simplest tree — it’s just a single leaf.

```
Leaf
```

Here is a tree with one `Node`

containing value 3, and two leaves.

```
Node 3 Leaf Leaf
```

If you type this into ghci, you will see the values returned when you construct
these trees, so long as your `Tree`

datatype derives the `Show`

type class.

Look at the type of this value in ghci :

```
let l = Node 3 Leaf Leaf
:t l
```

Look at the type of the constructor Node:

```
:t Node
```

This is a function: the constructor `Node`

takes three arguments and
returns a `Tree`

result.

Now let’s write a function to compute the depth of a `Tree`

—
this is the maximum number of branches from the root to any leaf.
To write this function, we will do pattern matching on the
different kinds of `Tree`

, i.e. `Leaf`

and `Node`

values.
Each `Leaf`

is a base case, but for each `Node`

, we
need to recursively process the two child trees.

```
treeDepth :: Tree -> Int
treeDepth Leaf = 0
treeDepth (Node _ leftSubtree rightSubtree) =
1 + max (treeDepth leftSubtree) (treeDepth rightSubtree)
```

Notice the `_`

in line 3, which is a ‘don’t care’ value, since we discard the `Int`

payload
in each `Node`

.

You can imagine how to write a very similar
function that traverses a tree and adds up all the values in
its nodes. Have a go at writing this, maybe call it `treeSum`

.

Here is its type:

```
treeSum :: Tree -> Int
```

How about a function to check whether a tree is sorted properly?
The data structure invariant we want is
that, for any `Node`

storing value `x`

, all values in its left subtree are
`< x`

, and all values in its right
subtree are `>= x`

.

So this function will take in a `Tree`

, a minimum value,
a maximum value and it will return a `Bool`

.
isSortedTree :: Tree -> Int -> Int -> Bool

A `Leaf`

is automatically sorted, since it does not contain a value.
For each `Node`

, we have to check the value in it
is between the min and max values,
which start off as far apart as possible,
then get split into smaller ranges based on the value at the `Node`

.

```
isSortedTree :: Tree -> Int -> Int -> Bool
isSortedTree Leaf _ _ = True
isSortedTree (Node x leftSubtree rightSubtree) minVal maxVal =
let leftSorted = isSortedTree leftSubtree minVal x
rightSorted = isSortedTree rightSubtree x maxVal
in x >= minVal && x< maxVal && leftSorted && rightSorted
```

You can download this Haskell source code below, in file sortedtree.hs. Load the file into ghci: :l sortedtree.hs

(assuming you are in right directory) then invoke the function from the ghci prompt:

```
isSortedTree (Node 2 (Node 1 Leaf Leaf) (Node 3 Leaf Leaf)) minBound maxBound
```

where `minBound`

is defined as the smallest possible `Int`

value,
and `maxBound`

is the largest.

Let’s look at one more function for now.
So far, we have studied tree *traversal* functions,
where we go through the tree data structure and do some
incremental computation at each node.
Now we want to make a tree *modification* function.
This generates a new `Tree`

that is a modified version of the input `Tree`

.

The particular function we are going to define inserts a
new *maximum* value.
We go through the input `Tree`

until we find the rightmost node
with a `Leaf`

on the right, then we then replace this rightmost `Leaf`

with a new `Node`

containing a new max value
(one larger than previous max value).

```
addNewMax :: Tree -> Tree
-- add a new max element to tree
addNewMax Leaf = Node 0 Leaf Leaf -- input tree with no nodes
addNewMax (Node x t1 Leaf) = Node x t1 (Node (x+1) Leaf Leaf) -- this is the rightmost Node
addNewMax (Node x t1 t2) = Node x t1 (addNewMax t2) -- intermediate node, go down right subtree
```

This `addNewMax`

function takes a `Tree`

input value
and returns a `Tree`

output value.
You can download this code from `addnewmax.hs`

below, and load it into ghci.
Note the function does not do a *destructive* update — the old
input `Tree`

remains unchanged.
We have created a new data structure, which has some nodes shared with the
original `Tree`

. Search online for
*purely functional data structures* to find out more information about
this concept.

Next you need to write some `Tree`

functions for yourself.
Download the `sortedtree.hs`

file below and load it into GHCi.
Can you write functions to insert a value into a `Tree`

in order, or to
convert from a `Tree`

into a list?

© University of Glasgow