Scala Binary Search Tree
EmptyBST.min

Since min can only return type T, EmptyBST.min has to throw an exception.  There is no logical alternative.

You could consider also implementing minOption: Option[T], which gives the caller more flexibility. Then EmptyBST.minOption would return None.

Tail recursion

None of your methods are tail recursive - not even the simple ones min and search.  You can test this by placing @annotation.tailrec before any of them. The compiler will give an error.

min and search

These cannot be tail recursive, even though the calls to l.min or left.search/right.search seem to be in tail positions. Class methods (as opposed to object methods - functions, in other words) have to be final or private and have to call themselves, not - as you are doing - a superclass method.

For these two methods, this can be solved simply.  One way is to use a while loop and a var to descend the branch (this is how many methods in the collections library do it).  Another is to use an internal helper function like this (for NonEmptyBST.min):

def min : T = {
  @annotation.tailrec
  def go(node: NonEmptyBST[T]): T = node.left match {
    case EmptyBST() =&gt; value
    case l: NonEmptyBST[T] =&gt; go(l)
  }
  go(this)
}


search can be fixed in the same fashion.

Updating the tree safely

Removals and insertions are much harder to do safely (that is, without risking stack overflow) in a functional, immutable tree. It is much easier in a mutable tree, where an insertion will only modify one node.  In an immutable tree, the final node and each node back down the path has to be modified.

The best way I know to do this is with a zipper.  Zippers allow you to navigate the tree with a minimum of copying to the point where the modification should be made.  Once that is done, the tree can be reconstructed from the zipper (again with a minimum of copying).  I could write a zipper implementation here but as it happens this set of slides begins with a description of how to write one for a binary tree like yours. You can stop once you get to "A Zipper Complete" - that shows you enough for this problem.

If you are still struggling after reading the slides, let me know and I will update this answer.

Easier building

For building a BST from a given set of values, it would be useful for you to modify your apply method to take a sequence of values of type T as input.  That would allow you to create a BST from a list in one concise line of code.