Functional programming in Scala, Chapter 3, Tree implementation

object Example {

  sealed trait Tree[+A]

  case class Leaf[A](value: A) extends Tree[A]

  case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

  def size(tree: Tree[_]): Int = {
    tree match {
      case _: Leaf[_] => 1
      case x: Branch[_] => size(x.left) + size(x.right)
    }
  }
  def size1[A](tree: Tree[A]): Int = {
    fold[A, Int](tree)(a => 1)(_ + _)
  }
  def maximum(tree: Tree[Int]): Int = tree match {
    case l: Leaf[_] => l.asInstanceOf[Leaf[Int]].value
    case b: Branch[_] => maximum(b.left.asInstanceOf[Tree[Int]]) max maximum(b.right.asInstanceOf[Tree[Int]])
  }
  def maximum1(tree: Tree[Int]): Int = fold(tree)(a => a)(_ max _)

  def depth(tree: Tree[_]): Int = tree match {
    case _: Leaf[_] => 0
    case b: Branch[_] => (depth(b.left) max depth(b.right)) + 1
  }
  // https://docs.google.com/drawings/d/1Ap5Azj1Axy8bgWPnrkm_2XC8H_YJ4imRcU3VqXXjMSU/edit?usp=sharing
  def depth1(tree: Tree[_]): Int = {
    // Leaf has level 0
    fold(tree)(a => 0)((d1, d2) => 1 + (d1 max d2))
  }

  def map[A, B](tree: Tree[A])(f: A => B): Tree[B] = tree match {
    case l: Leaf[_] => Leaf(f(l.asInstanceOf[Leaf[A]].value))
    case b: Branch[_] => {
      val b1 = b.asInstanceOf[Branch[A]]
      Branch(map(b1.left)(f), map(b1.right)(f))
    }
  }

  def map1[A, B](tree: Tree[A])(f: A => B): Tree[B] =
    fold(tree)(a => Leaf(f(a)): Tree[B])(Branch(_, _))

  def fold[A, B](tree: Tree[A])(f: A => B)(g: (B, B) => B): B = tree match {
    case Leaf(a) => f(a)
    case Branch(b1, b2) => {
      g(fold(b1)(f)(g), fold(b2)(f)(g))
    }
  }
}


object Test {

  import Example._

  val t = Branch(Leaf(1), Branch(Leaf(1), Leaf(13)))
  size(t)
  depth(t)
  depth1(t)
  maximum(t)
  maximum1(t)
  map(t)(x => x + 1)
  map1(t)(x => x + 1)
}