Scala Binary Search Tree

Question

In an attempt to get deeper down into Scala, I decided to make a BST using as many interesting concepts as possible in order to explore everything Scala has to offer.

Taking inspiration from this question/accepted answer, I wrote:

package bst

object BST {
  def apply[T <% Ordered[T]]() : BST[T] = new EmptyBST[T]()
}

abstract sealed class BST[T <% Ordered[T]] {
  def insert(e: T) : BST[T]
  def remove(value: T) : BST[T]
  def search(e: T) : Boolean
  def min : T
}

case class EmptyBST[T <% Ordered[T]]() extends BST[T] {
  def insert(e: T) : BST[T] = NonEmptyBST[T](EmptyBST[T](), EmptyBST[T](), e)
  def remove(value: T) : BST[T] = this
  def search(e: T) : Boolean = false
  def min : Nothing = ??? ///Uncertain of how to handle this
}

case class NonEmptyBST[T <% Ordered[T]](left: BST[T], right: BST[T], value: T) extends BST[T] {

  def min : T = this.left match {
    case EmptyBST() => this.value
    case NonEmptyBST(l, _, _) => l.min
  }

  def insert(e: T) : BST[T] = e match {
    case this.value => this
    case `e` if e > value => NonEmptyBST[T](left, right.insert(e), value) 
    case _ => NonEmptyBST[T](left.insert(e), right, value)
  }

  def remove(target: T) : BST[T] = target match {
    case this.value => this match {
    case NonEmptyBST(EmptyBST(), EmptyBST(), _) => EmptyBST()
    case NonEmptyBST(EmptyBST(), r, _) => r
    case NonEmptyBST(l, EmptyBST(), _) => l
    case NonEmptyBST(l, r, _) => val min = r.min
                 NonEmptyBST(l, r.remove(min), min)
    }
    case _ if target > this.value => NonEmptyBST(left, right.remove(target), value)
    case _ => NonEmptyBST(left.remove(target), right, value)
  }

  def search(target: T) : Boolean = target match {
    case `value` => true
    case _ if value > target => left.search(target) 
    case _ => right.search(target)
  }
}

I would love to hear about how I could improve this. My intention with this is to have practice using some of Scala's more powerful tools, so feel free to suggest improvements that would otherwise be unecessarily complex for something like this.

Something that I'm specifically looking for guidance on is commented as such. It is the min method from EmptyBST.

Answer 1

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() => value
    case l: NonEmptyBST[T] => 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.