object TailRecursiveTreeFold {

  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 fold[A, B](tree: Tree[A],
                 f: A => B,
                 g: (B, B) => B): B = {

    def helper(rest: List[Tree[A]],
               acc: Option[B]): B = rest match {
      case Nil => acc.get // trust me
      case Leaf(a)::ls if acc.isEmpty => helper(ls, Some(f(a)))
      case Leaf(a)::ls => helper(ls, Some(g(acc.get, f(a))))
      case Branch(l, r)::ls => helper(r::l::ls, acc)
    }

    helper(List(tree), None)
  }
}