tree.scala

trait Tree[+A] {
  def insert[B >: A <% Ordered[B]](b: B): Tree[B]
  def contains[B >: A <% Ordered[B]](element: B): Boolean
}

case class Node[+A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] {

  def insert[B >: A <% Ordered[B]](b: B): Tree[B] = b.compare(value) match {
    case x if x < 0 => Node(value, left.insert(b), right)
    case 0 => this
    case x if x > 0 => Node(value, left, right.insert(b))
  }

  def contains[B >: A <% Ordered[B]](element: B): Boolean = element.compare(value) match {
    case x if x < 0 => left.contains(element)
    case 0 => true
    case x if x > 0 => right.contains(element)
  }

}

case object EmptyTree extends Tree[Nothing] {
  def insert[B >: Nothing <% Ordered[B]](b: B) = Tree(b)
  def contains[B >: Nothing <% Ordered[B]](element: B) = false
}

object Tree {
  def empty[A]: Tree[A] = EmptyTree
  def apply[A](a: A): Tree[A] = Node(a, EmptyTree, EmptyTree)
  def fromTraversable[A <% Ordered[A]](trav: Traversable[A]) =
    trav.foldLeft(empty[A]) {(tree, a) => tree.insert(a)}
}

case class Widget[A](a: A)
case class IntWidget(i: Int) extends Widget(i)

implicit def widgetOrdering[A <% Ordered[A]] = new Ordering[Widget[A]] {
  def compare(w1: Widget[A], w2: Widget[A]): Int = {
    val Widget(a1) = w1
    val Widget(a2) = w2
    return a1.compare(a2)
  }
}

val widgets = List(3,2,6,1).map(Widget(_)) ++ List(1,0,2,4,7).map(IntWidget(_))
val tree = Tree.fromTraversable(widgets)
println(tree)
println(tree.contains(Widget(3)))