BinaryTree.scala

class BinaryTree[A <% Ordered[A]]private (datum: A,less: Option[BinaryTree[A]],more: Option[BinaryTree[A]]) {

            def this(datum: A) = this(datum, None,None)

            def add(a: A):BinaryTree[A] = {

                def addTo(branch: Option[BinaryTree[A]]) = Some(branch.map(_.add(a)).getOrElse(new BinaryTree(a)))

                if (a <= datum)
                    new BinaryTree(datum, addTo(less), more)
                else
                    new BinaryTree(datum,less, addTo(more))
            }

            def inOrder:Seq[A] = {
                def inOrder(branch: Option[BinaryTree[A]]) = branch.map(_.inOrder).getOrElse(Nil)
                inOrder(less) ++ List(datum) ++ inOrder(more)

            }

            def exists(a: A): Boolean = {

                val compare:Int = a.compareTo(datum)
                if (compare == 0) true
                else if (compare < 0)
                {
                    less.map(_.exists(a)).getOrElse(false)
                }
                else more.map(_.exists(a)).getOrElse(false)
            }
}