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
else if (elem < loadTree(tree)) Node(loadTree(tree), addToTree(elem, leftBranch(tree)), rightBranch(tree))
else Node(loadTree(tree), leftBranch(tree), addToTree(elem, rightBranch(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!