Immutable binary search tree using Scala

Question

I have written a sample immutable binary search tree using Scala. However, I am not sure whether or not I was doing it the proper way since I am not an expert at functional programming. Is there a better or more efficient way of, say, traversing the tree or adding an item to it using a purely functional approach?

The add (+) method:

def +(data: T): Bst = {
 def insert(optTree: OptBst): Bst = optTree match {
 case None => BST(data)(comparison)
 case Some(tree) => comparison(data, tree.data) match {
 case cmp if cmp < 0 => tree(left = Some(insert(tree.left)))
 case cmp if cmp > 0 => tree(right = Some(insert(tree.right)))
 case _ => tree
 }
 }
 insert(Some(this))
}

Delete (-) method:

def -(data: T): OptBst = {
 def remove(optTree: OptBst): OptBst = optTree match {
 case None => None
 case Some(tree) => comparison(data, tree.data) match {
 case cmp if cmp > 0 => Some(tree(right = remove(tree.right)))
 case cmp if cmp < 0 => Some(tree(left = remove(tree.left)))
 case _ => (tree.hasLeft, tree.hasRight) match {
 case (false, false) => None
 case (true, false) => tree.left
 case (false, true) => tree.right
 case (true, true) => 
 val rightMinData = tree.rightMin.get.data
 Some(tree(data = rightMinData, right = tree.right.get - rightMinData))
 }
 }
 }
 remove(Option(this))
}

Search method:

 def search(data: T) = {
 @tailrec
 def search(optTree: OptBst): OptBst = optTree match {
 case None => None
 case Some(tree) => comparison(data, tree.data) match {
 case cmp if cmp < 0 => search(tree.left)
 case cmp if cmp > 0 => search(tree.right)
 case _ => optTree
 }
 }
 search(Some(this))
 }

Answer 1

I think it would be an improvement to define an empty element. Currently you have no way to represent an empty collection. But that is required if you would want to integrate your data structure with scala collections.

(In scala collections, you usually build up an immutable data structure like a Set or Map by starting with the empty element and adding elements. The apply methods defined in the companion objects are just convenience methods)

Defining an empty element will also simplify your code a lot. For example: you won't have to use Option for left and right, but can just use the empty value if e.g. left does not contain elements. For iteration for example you don't have to check whether left or right is empty by checking for None, but just call the method on the child.

In the simplest case this will look something like this:

object BST {
 def empty[T](implicit c:(T,T) => Int) : BST[T] = new EmptyBST(c)
}
sealed abstract class BST[T] {
 // abstract: whatever methods you want to support
}
case class EmptyBST[T](c:(T,T) => Int) extends BST[T] {
 // trivial implementation of all methods for an empty BST
}
case class NonEmptyBST[T](left:BST[T], right:BST[T], value:T, c:(T,T) => Int) extends BST {
 // non-trivial implementation of all methods for the non-empty case
}

Another thing: using (T,T) => Int is perfectly fine for educational purposes. But if you want this to match the style of other scala collections, you should use scala.math.Ordering. There are already predefined orderings and some utility methods to create orderings for composite objects like tuples.

For the traversal, I would not return a List[T] of all elements but instead just implement the Traversable[T] trait by defining a foreach method for each traversal order. That is much more efficient in case the user is not interested in everything but just the first few elements. And if the user wants a List[T] he can always make one by calling .toList. Traversal using foreach uses side effects internally, but for the end user these are not observable, so it's OK.