import cats._

sealed trait Tree[+A]
final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
final case class Leaf[A](value: A) extends Tree[A]

object Tree {

  implicit val treeMonad: Monad[Tree] = new Monad[Tree]{
    override def pure[A](a: A): Tree[A] = Leaf(a)

    override def flatMap[A, B](fa: Tree[A])(f: A => Tree[B]): Tree[B] = fa match {
      case Branch(l, r) => Branch(flatMap(l)(f), flatMap(r)(f))
      case Leaf(a) => f(a)
    }
    override def tailRecM[A, B](a: A)(f: A => Tree[Either[A, B]]): Tree[B] = {
      def go(tree: Tree[Either[A, B]]): Tree[B] = tree match {
        case Leaf(Left(a)) => tailRecM(a)(f)
        case Leaf(Right(b)) => Leaf(b)
        case b@Branch(_, _) => go(b)
      }
      go(f(a))
    }
  }


}