Academic implementation of a binary tree in Scala.

BinaryTree.scala

// Written by Jämes Ménétrey for the lecture Advanced Programming Paradigms.
// Linear walk through inspired from https://gist.github.com/dholbrook/2967371.

import scala.annotation.tailrec
import scala.language.implicitConversions

object BinaryTreeImpl {

  /**
    * The contract that defines a binary tree.
    */
  abstract class BinaryTree[A](implicit ordering: Ordering[A]) {
    def +(x: A): BinaryTree[A] = add(x)
    def +(x: BinaryTree[A]): BinaryTree[A] = union(x)
    def -(x: A): BinaryTree[A] = excl(x)
    def add(x: A): BinaryTree[A]
    def contains(x: A): Boolean
    def excl(elems: A): BinaryTree[A]
    def foreach(f: A => Unit): Unit = iteratorInorder().foreach(f)
    def foldInorder[B](z: B)(op: (B, A) => B): B = iteratorInorder().foldLeft(z)(op)
    def foldPreorder[B](z: B)(op: (B, A) => B): B = iteratorPreorder().foldLeft(z)(op)
    def foldPostorder[B](z: B)(op: (B, A) => B): B = iteratorPostorder().foldLeft(z)(op)
    def intersect(other: BinaryTree[A]): BinaryTree[A]
    def isEmpty: Boolean
    def iteratorInorder(): Iterator[A] = new Iterators.InorderBinaryTreeIterator[A](this)
    def iteratorPreorder(): Iterator[A] = new Iterators.PreorderBinaryTreeIterator[A](this)
    def iteratorPostorder(): Iterator[A] = new Iterators.PostorderBinaryTreeIterator[A](this)
    def union(other: BinaryTree[A]): BinaryTree[A]
  }

  /**
    * The companion object to create binary trees.
    */
  object BinaryTree {
    /**
      * Creates a new binary tree from 0 to n elements.
      */
    def apply[A](elements: A*)(implicit ordering: Ordering[A]): BinaryTree[A] =
      elements.foldLeft(new EmptyBinaryTree[A](): BinaryTree[A]) { (acc, e) => acc add e }

    /**
      * Defines an implicit conversion from ordering element to binary trees, so methods can directly be called from.
      */
    implicit def AToBinaryTree[A](x: A)(implicit ordering: Ordering[A]): BinaryTree[A] = BinaryTree(x)
  }

  /**
    * A definition of a non empty binary tree.
    */
  class NonEmptyBinaryTree[A](val elem: A, val left: BinaryTree[A], val right: BinaryTree[A])(implicit val ordering: Ordering[A]) extends BinaryTree[A] {
    /**
      * Adds an element in the binary tree.
      *
      * Complexity: O(log n)
      */
    override def add(x: A): BinaryTree[A] = {
      if (ordering.lt(x, elem)) new NonEmptyBinaryTree[A](elem, left add x, right)
      else if (ordering.gt(x, elem)) new NonEmptyBinaryTree[A](elem, left, right add x)
      else this
    }

    /**
      * Determines whether the binary tree contains a given element.
      *
      * Complexity: O(log n)
      */
    override def contains(x: A): Boolean = {
      if (ordering.lt(x, elem)) left contains x
      else if (ordering.gt(x, elem)) right contains x
      else true
    }

    /**
      * Removes an element from the binary tree.
      *
      * Complexity: O(log n)
      */
    override def excl(x: A): BinaryTree[A] = {
      /**
        * Finds the deepest right element of the tree from a given node.
        */
      @tailrec
      def findDeepestRightElement(node: NonEmptyBinaryTree[A]): A = node.right match {
        case _: EmptyBinaryTree[A] => node.elem
        case right: NonEmptyBinaryTree[A] => findDeepestRightElement(right)
      }

      if(ordering.lt(x, elem)) new NonEmptyBinaryTree[A](elem, left excl x, right)
      else if(ordering.gt(x, elem)) new NonEmptyBinaryTree[A](elem, left, right excl x)
      else {
        left match {
          case _: EmptyBinaryTree[A] => right
          case l: NonEmptyBinaryTree[A] =>
            val replacementElement = findDeepestRightElement(l)
            new NonEmptyBinaryTree[A](replacementElement, left excl replacementElement, right)
        }
      }
    }

    override def isEmpty: Boolean = false

    /**
      * Intersects two binary trees using the merge algorithm.
      *
      * Complexity: O(n + m)
      */
    override def intersect(other: BinaryTree[A]): BinaryTree[A] = {
      val thisIterator = iteratorInorder()
      val otherIterator = other.iteratorInorder()

      @tailrec
      def iter(x: A, y: A, acc: BinaryTree[A]): BinaryTree[A] = acc match {
        case a if ordering.lt(x, y) => iter(thisIterator.next(), y, a)
        case a if ordering.gt(x, y) => iter(x, otherIterator.next(), a)
        case a if ordering.equiv(x, y) && !thisIterator.hasNext || !otherIterator.hasNext => a add x
        case a if ordering.equiv(x, y) => iter(thisIterator.next(), otherIterator.next(), a add x)
        case a => a
      }

      iter(thisIterator.next(), otherIterator.next(), new EmptyBinaryTree[A]())
    }

    /**
      * Formats all the nodes of the binary tree.
      *
      * Complexity: O(n)
      */
    override def toString: String = s"($left|$elem|$right)"

    /**
      * Unifies two binary trees.
      *
      * Complexity: O(m * log n)
      */
    def union(other: BinaryTree[A]): BinaryTree[A] = foldInorder(other) { (acc, e) => acc add e }
  }

  /**
    * A definition of an empty binary tree.
    */
  class EmptyBinaryTree[A]()(implicit ordering: Ordering[A]) extends BinaryTree[A] {
    override def add(x: A): BinaryTree[A] = new NonEmptyBinaryTree[A](x, new EmptyBinaryTree[A], new EmptyBinaryTree[A])

    override def contains(x: A): Boolean = false

    override def excl(elems: A): BinaryTree[A] = this

    override def intersect(other: BinaryTree[A]) = new EmptyBinaryTree[A]()

    override def isEmpty: Boolean = true

    override def toString: String = "-"

    def union(other: BinaryTree[A]): BinaryTree[A] = other
  }

  /**
    * Definition of the iterators of the binary trees.
    */
  object Iterators {

    /**
      * A type that indicates that the node of the tree must be evaluated when linearized through the method extractor.
      * This enables to walk through the tree using a tail recursion with different orders.
      */
    private class WaitingForEval[A](elem: A)(implicit ordering: Ordering[A]) extends NonEmptyBinaryTree[A](elem, null, null)

    class InorderBinaryTreeIterator[A](tree: BinaryTree[A])(implicit ordering: Ordering[A])
      extends BinaryTreeIterator(tree, (set: NonEmptyBinaryTree[A]) => List[BinaryTree[A]](set.left, new WaitingForEval(set.elem), set.right))

    class PreorderBinaryTreeIterator[A](tree: BinaryTree[A])(implicit ordering: Ordering[A])
      extends BinaryTreeIterator(tree, (set: NonEmptyBinaryTree[A]) => List[BinaryTree[A]](new WaitingForEval(set.elem), set.left, set.right))

    class PostorderBinaryTreeIterator[A](tree: BinaryTree[A])(implicit ordering: Ordering[A])
      extends BinaryTreeIterator(tree, (set: NonEmptyBinaryTree[A]) => List[BinaryTree[A]](set.left, set.right, new WaitingForEval(set.elem)))

    /**
      * The iterator of a binary tree. The tree is linearised to prevent extensive use of the stack.
      */
    abstract class BinaryTreeIterator[A](tree: BinaryTree[A], order: NonEmptyBinaryTree[A] => List[BinaryTree[A]]) extends Iterator[A] {
      // Scala doc recommends to use a var instead of a val stack. Let's face the reality, an iterator is stateful.
      var list: List[BinaryTree[A]] = removeEmptyTree(List(tree))

      override def hasNext: Boolean = list.nonEmpty

      override def next(): A = extractor(list)

      /**
        * Loops across the nodes of the binary tree using a tail recursion.
        */
      @tailrec
      private def extractor(l: List[BinaryTree[A]]): A = l match {
        case (h: WaitingForEval[A]) :: r => list = removeEmptyTree(r); h.elem
        case (h: NonEmptyBinaryTree[A]) :: r => list = removeEmptyTree(order(h)) ++ r; extractor(list)
        case _ => throw new UnsupportedOperationException("Cannot call next method with no element left in the iterator.")
      }

      private def removeEmptyTree(l: List[BinaryTree[A]]): List[BinaryTree[A]] = l.dropWhile(_.isEmpty)
    }
  }

}

import BinaryTreeImpl._

val s1 = BinaryTree[Int]()
  .add(2)
  .add(1)
  .add(3)
  .add(0)

s1.foldPreorder("") { (acc, e) => s"$acc[$e]" }
s1.foldPostorder("") { (acc, e) => s"$acc[$e]" }

s1.contains(3)
s1.contains(4)
s1.foreach(e => print(s"[$e]"))
BinaryTree(5, 4, 3, 2, 1).foldInorder(0)(_ + _)

//
// 1.c
//
s1.foreach(e => print(s"${e + 1}, "))

//
// 2.a
//
BinaryTree(1, 2, 3) union BinaryTree(4, 5, 6)

//
// 2.b
//
BinaryTree(1, 2, 3) intersect BinaryTree(3, 4, 1)

//
// 3.a
//
BinaryTree(5,3,4,2,1,8,7,9,6) excl 3

//
// 3.b
//
val s2 = BinaryTree[Int]() + 3 + 5 + 1 + 2

s2 - 3

// the implicit conversion is in the implicit scope because it is defined in the companion class AND there is
// a +(BinaryTree[A]) method. Indeed, scala compiler import the implicit scope of the argument's type.

3 + BinaryTree(2)