Binary Tree

TreeImpl.scala

import TreeImpl.Tree.{leaf, node}

object TreeImpl {

  sealed trait Tree[+A] {
    def value: A
    def map[B >: A](f: A => B): Tree[B]
    def flatMap[B >: A](f: A => Tree[B]): Tree[B]
    def withFilter(f: A => Boolean): Tree[Option[A]]
    def toList: List[A]
    def count: Int
  }

  final case class Leaf[+A](override val value: A) extends Tree[A] {
    override def map[B >: A](f: A => B): Tree[B] = leaf(f(value))
    override def flatMap[B >: A](f: A => Tree[B]): Tree[B] = f(value)
    override def withFilter(f: A => Boolean): Tree[Option[A]] = leaf(Some(value).filter(f))
    override def toList: List[A] = List(value)
    override def count: Int = 1
  }

  final case class Node[+A](override val value: A, left: Tree[A], right: Tree[A]) extends Tree[A] {
    override def map[B >: A](f: A => B): Tree[B] = node(f(value), left map f, right map f)
    override def flatMap[B >: A](f: A => Tree[B]): Tree[B] = node(f(value).value, left flatMap f, right flatMap f)
    override def withFilter(f: A => Boolean): Tree[Option[A]] = node(Some(value).filter(f), left withFilter f, right withFilter f)
    override def toList: List[A] = List(value) ::: left.toList ::: right.toList
    override def count: Int = 1 + left.count + right.count
  }

  object Tree {
    def leaf[A](value: A): Tree[A] = Leaf(value)
    def node[A](value: A, left: Tree[A], right: Tree[A]): Tree[A] = Node(value, left, right)
  }

  def main(args: Array[String]): Unit = {

    val tree: Tree[String] = node("",
      leaf("remember,"), node("when you feel bored",
        leaf("just get up and"), leaf("flatMap that shit!")))

    val sentence = tree.withFilter(_.nonEmpty)
      .toList
      .flatten
      .map(_.toUpperCase)
      .fold("")(_ concat " " concat _)
      .trim

    assert("REMEMBER, WHEN YOU FEEL BORED JUST GET UP AND FLATMAP THAT SHIT!" == sentence)
  }
}