A simple tree sealed trait with K key and V value types, has eulertour and is traversable

Tree.scala

sealed trait Tree[K, V] extends Traversable[Tree[K,V]] {
  self =>

  type Key = K
  type Value = V

  def eulerTourWithLevel[U, W, Y](level: Int)(in: Int => Tree[K, V] => U,
                                                middle: Int => Tree[K, V] => W,
                                                out: Int => Tree[K, V] => Y): Unit

  def nonEmpty: Boolean

  override def foreach[U](f: Tree[K, V] => U): Unit = eulerTourWithLevel(0)(
    _ => x => f(x),
    _ => _ => (),
    _ => _ => ()
  )

}


case class Node[K, V](left: Tree[K, V], right: Tree[K, V], k: K, v: V) extends Tree[K, V] {
  self =>
  override val nonEmpty = true

  def eulerTourWithLevel[U, W, Y](level: Int)
                                 (in: Int => Tree[K, V] => U,
                                  middle: Int => Tree[K, V] => W,
                                  out: Int => Tree[K, V] => Y): Unit = {
    in(level)(self)
    left.eulerTourWithLevel(level + 1)(in, middle, out)
    if (left.nonEmpty && right.nonEmpty) middle(level)(self)
    right.eulerTourWithLevel(level + 1)(in, middle, out)
    out(level)(self)
  }

  def withKeyValue(k: K, v: V) = self.copy(k = k, v = v)

  def withLeft(that: Tree[K, V]) = self.copy(left = that)

  def withRight(that: Tree[K, V]) = self.copy(right = that)

  def asParentOf(left: Tree[K, V], right: Tree[K, V]): Node[K, V] = self.copy(left = left, right = right)

  def asLeftOf(parent: Node[K, V]) = parent.copy(left = self)

  def asRightOf(parent: Node[K, V]) = parent.copy(right = self)

  override def toString(): String = s"Node [$left[ === ]$right] "

}


case class Empty[K, V]() extends Tree[K, V] {
  override val nonEmpty = false

  override def eulerTourWithLevel[U, W, Y](level: Int)(in: Int => Tree[K, V] => U, middle: Int => Tree[K, V] => W, out: Int => Tree[K, V] => Y): Unit = ()

  def withLeft(that: Node[K, V], k: K, v: V): Node[K, V] = withKeyValue(k, v).withLeft(that)

  def withKeyValue(k: K, v: V): Node[K, V] = Node(this, this, k, v)

  def withRight(that: Node[K, V], k: K, v: V): Node[K, V] = withKeyValue(k, v).withRight(that)

  override def toString(): String = "empty"
}