# 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
else recurse(elems.tail, bst + elems.head)

recurse(elems.toList, NonEmptyBST(elem, EmptyBST, EmptyBST))
}
}

• I remember seeing some academic paper about an efficient algorithm to implement an immutable binary tree. I know it was referenced in some way by Martin Odersky. Sorry, but it's really all that I remember. Jun 14, 2014 at 17:14
• 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.) Oct 24, 2017 at 5:33

I have not treated Scala, but Haskell. I like some competitive programming and I thought about Tree Problems deeply. I'm sorry for the Japanese site, a tree problem and my solution are:

Deque - Aizu Online Judge

My solution in Haskell

In Scala, the vector type scala.collection.immutable.Vector is similar to my above tree structure. Maybe, you can get faster implementation than the simple BST.

Each depth d needs 2^(d-1) nodes, I think the following relationship:

1st depth = 1
2nd depth = [2, 3]
3rd depth = [4, 5, 6, 7]


In general,

left = (parent << 1);
right = (parent << 1) + 1;
parent = child >> 1;

• Sorry for the delay, SE didn't notify me of your response. Thank you for the change your post should now meet the requirements to not be deleted. May 30, 2021 at 20:31