Tree.scala

object Tree {
  sealed trait Tree[A]
  case class Leaf[A](a: A) extends Tree[A]
  case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A]
  
  def translate[A, B, C, F[_], E](t: Tree[A], check: (A, B) => Boolean, newState: B => B, endState: (A, B) => C, err: A => E)(implicit F: MonadError[F, E]): StateT[F, B, Tree[C]] = t match {
    case Leaf(a) => StateT(s => if (check(a, s)) F.raiseError(err(a)) else F.pure((newState(s), Leaf(endState(a, s)))))
    case Node(left, right) =>
      implicit val A = Apply[StateT[F, B, ?]]
      (translate(left, check, newState, endState, err), translate(right, check, newState, endState, err)).mapN(Node.apply)
  }
  
}

val t = Node(Node(Leaf("a"), Leaf("b")), Leaf("c"))
println(translate[String, Int, Int, Either[Error, ?], Error](t, (_, y) => y > 1, _ + 1, (_, y) => y, x => new Error(s"boom at $x")).runA(0))