scala/ScalaBook/chapter-03/tree.scala

//abstract class Tree[+T]                         
//case object Leaf extends Tree[Nothing]
//case class Fork(elem: T, left: Tree[T], right: Tree[T])
//            extends Tree[T]
//def inOrder[T](t: Tree[T]): List[T] =    In-order traversal
//  t match {
//    case Leaf        => List()
//    case Fork(e,l,r) => inOrder(l):::List(e):::inOrder(r)
//  }
// 
// Haskell:
// data BinTree a = Empty | Node a (BinTree a) (BinTree a)
//




sealed abstract class BinTree                         
case object EmptyTree extends BinTree
case class  Node(elem: Int, left: BinTree, 
                            right: BinTree) extends BinTree

def inOrder(t: BinTree): List[Int] =    
  t match {
    case EmptyTree   => List()
    case Node(e,l,r) => inOrder(l):::List(e):::inOrder(r)
  }


def mkTree (l:List[Int]): BinTree = {
  def insert(x:Int, t:BinTree) : BinTree = {
    t match {
      case EmptyTree   => Node(x,EmptyTree,EmptyTree)
      case Node(y,l,r) => if (x < y) 
                            Node(y,insert(x,l),r)
                          else if (x > y)
                            Node(y,l,insert(x,r))
                          else 
                            EmptyTree
    }
  }
//
  l match {
    case Nil => EmptyTree
    case x::xs => insert(x,mkTree(xs))
  }
}

def max(x:Int, y:Int) = if (x>y) 
                          x
                        else
                          y

def depth(t: BinTree): Int = {
  t match {
    case EmptyTree => 0
    case Node(_,EmptyTree,r) => 1 + depth(r)
    case Node(_,l,EmptyTree) => 1 + depth(l)
    case Node(_,l,r) => max(depth(l),depth(r)) + 1
  }
}

def IsEmpty(t: BinTree): Boolean = 
  t match {
    case EmptyTree => true
    case _         => false
  }

def printRoot(t: BinTree):Unit =
   t match {
     case EmptyTree   => print("")
     case Node(x,l,r) => println(x)
   }
var EOF = false
var x:Int = _
var In:List[Int] = List()

do {
  print("gimme a number?\n? ")
  try { 
    x = readInt()        
  } catch {
     case e: java.io.IOException => EOF = true
  }
  if (! EOF) {
    In = x::In                     
  }
} while (! EOF)

println(IsEmpty(EmptyTree))
var z = mkTree(In)
print("depth of tree is ")
println(depth(z))
println(IsEmpty(z))
print(inOrder(z))
println(z)
println("===================")
printRoot(z)