## Wednesday, 8 March 2017

### Scala Trees

Recently, I've been playing with functional programming, ADT to be precise, and this is the outcome - trees implementation in Scala.
Data are created in common way as a Scala trait:

```sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]```

All looks Okay, lets create some trees and functions.

`val tree = Node(10, Node(5, EmptyTree, EmptyTree), Node(15, EmptyTree, EmptyTree))`

No problem, but at least for integer binary trees, we can right now do better: create a function to join elements to the tree:

```def addToTree(elem: Int, tree: Tree[Int]): Tree[Int] = {
if (isTreeEmpty(tree)) Node(elem, EmptyTree, EmptyTree)
else if (elem == loadTree(tree)) tree
}```

This is the standard way to add elements to a binary tree, we can use it in a loop and don't need to worry about memory - we use persistent data structure.

Two sample functions operate on a tree:

```def length[A](tree: Tree2[A]): Int =
tree match {
case EmptyTree => 0
case Node(x, left, right) => length2(left) + 1 + length2(right)
} ```

```def maxDepth[A](tree: Tree2[A]): Int =
tree match {
case EmptyTree => 0
case Node(x, left, right) =>
var lmax = maxDepth2(left)
var rmax = maxDepth2(right)
if (lmax > rmax) lmax + 1
else rmax + 1
}```

They do what their names promise: count nodes and maximum depth of the trees. Finally map over the tree:

```def treeMap[A, B](tree: Tree2[A])(f: A => B): Tree2[B] =
tree match {
case EmptyTree => EmptyTree
case Node(x, left, right) =>
Node(f(x), tree2Map(left)(f), tree2Map(right)(f))
}```
We can, in a similar way, all the needed function like foldl, traversing a tree and more. Code, including not implemented here functions helped to design joining element to tree, as usually on github. Till the next time!