FunctionalBST.scala

sealed abstract class BinaryTreeNode[+T] {
  def value: T
  def left: BinaryTreeNode[T]
  def right: BinaryTreeNode[T]
  def insert[U >: T <% Ordered[U]](x: U): BinaryTreeNode[U]
  def isEnd: Boolean
}

case class BSTNode[+T](
  value: T,
  left:  BinaryTreeNode[T],
  right: BinaryTreeNode[T]
) extends BinaryTreeNode[T] {

  def insert[U >: T <% Ordered[U]](elem: U): BinaryTreeNode[U] = {
    if (elem < value) {
      BSTNode(value, left.insert(elem), right)
    } else {
      BSTNode(value, left, right.insert(elem))
    }
  }
  override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"

  val isEnd = false
}

object BinaryTreeNode {
  def inOrder[T](node: BinaryTreeNode[T]): List[T] = node match {
    case BSTEnd => Nil
    case BSTNode(value, left, right) =>
      inOrder(left) ::: List(node.value) ::: inOrder(right)
  }

  def preOrder[T](node: BinaryTreeNode[T]): List[T] = node match {
    case BSTEnd => Nil
    case BSTNode(value, left, right) =>
      node.value :: preOrder(left) ::: preOrder(right)
  }

  def postOrder[T](node: BinaryTreeNode[T]): List[T] = node match {
    case BSTEnd => Nil
    case BSTNode(value, left, right) =>
      postOrder(left) ::: postOrder(right) ::: List(node.value)
  }

  def breadthFirst[T](node: BinaryTreeNode[T]): List[T] = {
    val queue = scala.collection.mutable.Queue[BinaryTreeNode[T]](node)
    var items = scala.collection.mutable.ListBuffer[T]()

    while(!queue.isEmpty) {
      val nextNode = queue.dequeue()
      if (!nextNode.isEnd) {
        items += nextNode.value
        queue.enqueue(nextNode.left, nextNode.right)
      }
    }
    items.toList
  }

  def bfsForeach[T](node: BinaryTreeNode[T])(f: (T, Int) => Unit): Unit = {
    val queue = scala.collection.mutable.Queue[(BinaryTreeNode[T], Int)]((node, 0))
    while(!queue.isEmpty) {
      val (nextNode, level) = queue.dequeue()
      if (!nextNode.isEnd) {
        f(nextNode.value, level)
        queue.enqueue((nextNode.left, level+1), (nextNode.right, level+1))
      }
    }
  }

  def depthFirst[T](node: BinaryTreeNode[T]): List[T] = {
    val stack = scala.collection.mutable.Stack[BinaryTreeNode[T]](node)
    var items = scala.collection.mutable.ListBuffer[T]()

    while(!stack.isEmpty) {
      val nextNode = stack.pop()
      if (!nextNode.isEnd) {
        items += nextNode.value
        stack.push(nextNode.left, nextNode.right)
      }
    }
    items.toList
  }

  def dfsForeach[T](node: BinaryTreeNode[T])(f: (T, Int) => Unit): Unit = {
    val stack = scala.collection.mutable.Stack[(BinaryTreeNode[T], Int)]((node, 0))

    while(!stack.isEmpty) {
      val (nextNode, level) = stack.pop()
      if (!nextNode.isEnd) {
        f(nextNode.value, level)
        stack.push((nextNode.left, level+1), (nextNode.right, level+1))
      }
    }
  }

  def fromList[U <% Ordered[U]](items: List[U]): BinaryTreeNode[U] = {
    var bst: BinaryTreeNode[U] = BSTEnd
    items foreach { item => 
      bst = bst.insert(item)
    }
    bst
  }
}

case object BSTEnd extends BinaryTreeNode[Nothing] {
  override def toString = "."
  def insert[U <% Ordered[U]](x: U) = BSTNode(x, BSTEnd, BSTEnd)

  def value = throw new Exception("no value for an empty node")
  def left = throw new Exception("no left tree for an empty node")
  def right = throw new Exception("no right tree for an empty node")

  val isEnd = true
}

val node = BinaryTreeNode.fromList(List(5,4,6,3,7,2,8,1,9,10,0))
val balanced = BinaryTreeNode.fromList(List(5,3,1,2,7,4,10))

var lastLevel = -1
BinaryTreeNode.bfsForeach(node) { (elem, level) =>
  if (level > lastLevel) {
    lastLevel = level
    println("")
  }
  print(elem+" ");
}

var lastLevel = -1
BinaryTreeNode.bfsForeach(balanced) { (elem, level) =>
  if (level > lastLevel) {
    lastLevel = level
    println("")
  }
  print(elem+" ");
}