# Binary Search Tree Monad Implementation

I've written a Binary Search Tree Monad in Scala. I would like to hear your thoughts on how to improve it (e.g. making insertion/deletion/search faster and more scalable). Also, is there a better way to implement this kind of data structure the Scala way?

The whole code

Here is the trait:

trait BST[+A] {
def +[B >: A <% Ordered[B]](elem: B): BST[B]
def ++[B >: A <% Ordered[B]](bst: BST[B]): BST[B]
def -[B >: A <% Ordered[B]](elem: B): (Option[B], BST[B])

def exists(p: A => Boolean): Boolean
def contains[B >: A <% Ordered[B]](e: B): Boolean
def filter[B >: A <% Ordered[B]](p: A => Boolean): BST[B] = filterAcc[B](EmptyBST)(p)
def filterAcc[B >: A <% Ordered[B]](acc: BST[B])(p: A => Boolean): BST[B]

def flatMap[B <% Ordered[B]](f: A => BST[B]): BST[B]
def map[B <% Ordered[B]](f: A => B): BST[B]

def inOrder[B](z: B)(f: (A, B) => B): B
def preOrder[B](z: B)(f: (A, B) => B): B
def postOrder[B](z: B)(f: (A, B) => B): B
def levelOrder[B](z: B)(f: (A, B) => B): B

def withLeft[B >: A <% Ordered[B]](newLeft: BST[B]): BST[B]
def withRight[B >: A <% Ordered[B]](newRight: BST[B]): BST[B]
def orElse[B >: A <% Ordered[B]](tree: BST[B]): BST[B]
def minChild[B >: A <% Ordered[B]]: BST[B] = minChildAcc[B](this)
def minChildAcc[B >: A <% Ordered[B]](acc: BST[B]): BST[B]

def toList = preOrder(List[A]())(_ :: _).reverse
}


And here is the implementation:

case object EmptyBST extends BST[Nothing] {
def +[B <% Ordered[B]](elem: B) = BST(elem)
def ++[B <% Ordered[B]](bst: BST[B]) = bst
def -[B <% Ordered[B]](elem: B) = (None, EmptyBST)

def flatMap[B <% Ordered[B]](f: Nothing => BST[B]): BST[B] = EmptyBST
def map[B <% Ordered[B]](f: Nothing => B): BST[B] = EmptyBST

def exists(p: Nothing => Boolean) = false
def contains[B <% Ordered[B]](e: B) = false
def filterAcc[B <% Ordered[B]](acc: BST[B])(p: Nothing => Boolean) = acc

def inOrder[B](z: B)(f: (Nothing, B) => B) = z
def preOrder[B](z: B)(f: (Nothing, B) => B) = z
def postOrder[B](z: B)(f: (Nothing, B) => B) = z
def levelOrder[B](z: B)(f: (Nothing, B) => B) = z

def withLeft[B <% Ordered[B]](newLeft: BST[B]) = newLeft
def withRight[B <% Ordered[B]](newRight: BST[B]) = newRight
def orElse[B <% Ordered[B]](tree: BST[B]) = tree
def minChildAcc[B <% Ordered[B]](acc: BST[B]) = acc

override def toString = "[]"
}

case class NonEmptyBST[A <% Ordered[A]](elem: A, left: BST[A], right: BST[A]) extends BST[A] {
def +[B >: A <% Ordered[B]](newElem: B) =
if (newElem < elem) withLeft(left + newElem)
else if (newElem > elem) withRight(right + newElem)
else this

def ++[B >: A <% Ordered[B]](bst: BST[B]) = bst.preOrder[BST[B]](this)((e, acc) => acc + e)

def -[B >: A <% Ordered[B]](e: B) =
if (e < elem) (left - e) match {
case (opt, l) => (opt, withLeft(l))
} else if (e > elem) (right - e) match {
case (opt, r) => (opt, withRight(r))
} else (Some(elem), (left, right) match {
case (EmptyBST, EmptyBST) => EmptyBST
case (l, EmptyBST) => l
case (EmptyBST, r) => r
case (l, r) => right.minChild match {
case EmptyBST => r.withLeft(l)
case NonEmptyBST(min, _, _) => NonEmptyBST(min, l, (r - min)._2)
}
})

def exists(p: A => Boolean) = p(elem) || left.exists(p) || right.exists(p)
def contains[B >: A <% Ordered[B]](e: B) = exists(_ == e)
def filterAcc[B >: A <% Ordered[B]](acc: BST[B])(p: A => Boolean) =
right.filterAcc(left.filterAcc(if (p(elem)) acc + elem else acc)(p))(p)

def flatMap[B <% Ordered[B]](f: A => BST[B]) = preOrder(f(elem))((e, acc) => acc ++ f(e))
def map[B <% Ordered[B]](f: A => B) = preOrder[BST[B]](BST(f(elem)))((e, acc) => acc + f(e))

def inOrder[B](z: B)(f: (A, B) => B) = right.inOrder(f(elem, left.inOrder(z)(f)))(f)
def preOrder[B](z: B)(f: (A, B) => B) = right.preOrder(left.preOrder(f(elem, z))(f))(f)
def postOrder[B](z: B)(f: (A, B) => B) = f(elem, right.postOrder(left.postOrder(z)(f))(f))

def levelOrder[B](z: B)(f: (A, B) => B) = {
def recurse(acc: B, queue: Queue[BST[A]]): B = queue match {
case Queue() => acc
case h +: t => h match {
case EmptyBST => recurse(acc, t)
case NonEmptyBST(e, l, r) => recurse(f(e, acc), t.enqueue(l).enqueue(r))
}
}

recurse(z, Queue(this))
}

def withLeft[B >: A <% Ordered[B]](newLeft: BST[B]) = NonEmptyBST(elem, newLeft, right)
def withRight[B >: A <% Ordered[B]](newRight: BST[B]) = NonEmptyBST(elem, left, newRight)
def minChildAcc[B >: A <% Ordered[B]](acc: BST[B]) = left.minChildAcc(this)
def orElse[B >: A <% Ordered[B]](tree: BST[B]) = this

override def toString = elem + "[l=" + left + ", r=" + right + "]"
}

object BST {
def apply[A <% Ordered[A]](): BST[A] = EmptyBST

def apply[A <% Ordered[A]](elem: A, elems: A*): BST[A] = {
def recurse(elems: List[A],bst: BST[A]): BST[A] =
if (elems.isEmpty) bst

• It does not sound right that you are using possibly different Ordered implementations on each operation. (Also, nowadays -I understand this is quite old question- Ordering and context bounds are preferred.) – Gábor Bakos Oct 24 '17 at 5:33