import ComparableWithOperator.comparable2operators

abstract class BST[T <: Comparable[T]] {

  val isBlack = true

  def value: T

  val left: BST[T]

  val right: BST[T]

  def add(x: T): BST[T]

  def in(x: T): Boolean

  def remove(x: T): BST[T]

  def isEmpty: Boolean

  def min: T

  def max: T

  def +(x: T) = add(x)

  def -(x: T) = remove(x)

  def ++(s: Seq[T]): BST[T] = s match {
    case head :: tail => this + s.head ++ s.tail
    case Nil => this
  }
}

class Node[T <: Comparable[T]](val value: T, override val left: BST[T] = new Nil[T], override val right: BST[T] = new Nil[T]) extends BST[T] {


  override def add(x: T): BST[T] = {
    if (x < value) new Node[T](value, left + x, right)
    else if (x > value) new Node[T](value, left, right + x)
    else this
  }

  override def in(x: T): Boolean = {
    if (x < value) left in x
    else if (x > value) right in x
    else true
  }

  override def toString = "{" + left + value + right + "}"

  override def remove(x: T) = {
    if (x < value) new Node(value, left.remove(x), right)
    else if (x > value) new Node(value, left, right.remove(x))
    else {
      if (isLeaf) new Nil[T]
      else if (right.isEmpty) left
      else if (left.isEmpty) right
      else {
        val succ = right.min
        new Node(succ, left, right.remove(succ))
      }
    }
  }

  def isLeaf = left.isEmpty && right.isEmpty

  override def isEmpty: Boolean = false

  override def min: T = if (left.isEmpty) value else left.min

  override def max: T = if (right.isEmpty) value else right.max
}

class Nil[T <: Comparable[T]] extends BST[T] {
  override def add(x: T): BST[T] = new Node[T](x)

  override def in(x: T): Boolean = false

  override def toString = "."

  override def remove(x: T) = this

  override def isEmpty: Boolean = true

  override def min: T = throw new IllegalStateException("there is no min")

  override def max: T = throw new IllegalStateException("there is no min")

  override def value: T = throw new IllegalStateException("there is no value")
  override val left: BST[T] = null
  override val right: BST[T] = null
}