Tree.scala

sealed trait TreeSeq[+A] {

  lazy val size: Int = this match {
    case Leaf(_) => 1
    case Branch(l, r) => (l.size + r.size)
  }

  def +[A1 >: A](a1: A1): TreeSeq[A1] = TreeSeq(a1)


  def ++[A1 >: A](tree: TreeSeq[A1]): TreeSeq[A1] =  tree

  def toVector1: Vector[A] = fold(x => Vector(x))(_ ++ _)
  def size1: Int           = fold(x => 1)(_ + _)


  def map[B](f: A => B): TreeSeq[B] = this match {
    case Leaf(v) => Leaf(f(v))
    case Branch(l, r) => Branch(l.map(f), r.map(f))
  }

  lazy val depth: Int = this match {
    case Leaf(_) => 1
    case Branch(l, r) => (l.depth + r.depth)
  }

  def pprint: String = this match {
    case Leaf(v) => v.toString
    case Branch(l, r) => (l, r).toString()
  }


  def fold[B](leaf: A => B)(branch: (B, B) => B): B = this match {
    case Leaf(v) => leaf(v)
    case Branch(l, r) => branch(l.fold(leaf)(branch), r.fold(leaf)(branch))
  }

  def toVector: Vector[A] = this match {
    case Leaf(v) => Vector(v)
    case Branch(l, r) => Vector(l.toVector, r.toVector).flatten
  }


}

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

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

object TreeSeq {

  def single[A](value: A): TreeSeq[A] = Leaf(value)

  def apply[A](head: A, tail: A*): TreeSeq[A] = {
    tail.foldLeft(single(head))(_ + _)
  }
}