BST.scala

package prep

class BST[E <: Ordered[E]](root: Node[E]) {
  def this() = this(Empty())

  lazy val seq = root.seq

  def + (e: E): BST[E] = new BST(root + e)
  def smallest(k: Int): E = seq(seq.size - k)
}

object BST {
  def apply = new BST
}

trait Node[E <: Ordered[E]] {
  def + (e: E): Node[E]
  //def - (e: E): Node
  def seq: IndexedSeq[E]
}

case class Empty[E <: Ordered[E]]() extends Node[E] {
  def + (e: E): Node[E] = NonEmpty(Empty(), e, Empty())
  def seq = IndexedSeq.empty[E]
}

case class NonEmpty[E <: Ordered[E]](l: Node[E], e: E, r: Node[E]) extends Node[E] {
  def + (e: E): Node[E] = 
    if (e < this.e) NonEmpty(l + e, this.e, r) 
    else if (e > this.e) NonEmpty(l, this.e, r + e)
    else this
  def seq = (l.seq :+ e) ++ r.seq
}

contains, -