Conc.scala

sealed trait Conc[+T] {
  def level: Int
  def size: Int
  def left: Conc[T] = throw new NoSuchElementException("no left subtree")
  def right: Conc[T] = throw new NoSuchElementException("no right subtree")

  def <>[U >: T](that: Conc[U]): Conc[U] = {
    if (this == Empty) that
    else if (that == Empty) this
    else concat(this, that)
  }

  private def concat[U](xs: Conc[U], ys: Conc[U]): Conc[U] = {
    val diff = ys.level - xs.level
    if (math.abs(diff) <= 1) new <>(xs, ys)
    else if (diff < -1) { // xs is more than one level taller.
      if (xs.left.level >= xs.right.level) {
        val nr = concat(xs.right, ys)
        new <>(xs.left, nr)
      } else {
        val nrr = concat(xs.right.right, ys)
        if (nrr.level == xs.level - 3) {
          val nl = xs.left
          val nr = new <>(xs.right.left, nrr)
          new <>(nl, nr)
        } else {
          val nl = new <>(xs.left, xs.right.left)
          val nr = nrr
          new <>(nl, nr)
        }
      }
    } else { // ys is more than one level taller.
      ???
    }
  }
}
case object Empty extends Conc[Nothing] {
  def level = 0
  def size = 0
}
class Single[T](val x: T) extends Conc[T] {
  def level = 0
  def size = 1
}
case class <>[T](override val left: Conc[T], override val right: Conc[T]) extends Conc[T] {
  val level = 1 + math.max(left.level, right.level)
  val size = left.size + right.size
}