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))
}