BinarySearchTrees

BinarySearchTrees.scala

package org.example

import scala.annotation.tailrec

// Made it a case class so you get the extras with no code
// changed the names to conform with the scala style
case class TreeNode[T](value: T, leftChild: Option[TreeNode[T]], rightChild: Option[TreeNode[T]]) {

  // Simple recursive traversal using pattern matching
  def mkString(sep: String = ", "): String = this match {
    case TreeNode(v, None, None) => v.toString
    case TreeNode(v, Some(l), Some(r)) => l.mkString(sep) + sep + v.toString + sep + r.mkString(sep)
    case TreeNode(v, Some(l), None) => l.mkString(sep) + sep + v.toString
    case TreeNode(v, None, Some(r)) => v.toString + sep + r.mkString(sep)
  }

  // Simplest traversal using the fact that None.toList is same as the empty list, while Some(t).toList is the same as List(t)
  // we can use list.mkString to print it as we wish
  def mkList: List[T] = leftChild.toList.flatMap(_.mkList) ::: List(value) ::: rightChild.toList.flatMap(_.mkList)

  // Traversal using tail recursive accumulating function
  // This will perform better than the previous function, in terms of speed,
  // and it will create a "loop" consuming less stack space
  // We can additionally use StringBuilder to improve performance on string operations
  def mkStringTR(sep: String = ", "): String = {
    @tailrec
    def acc(tn: Option[TreeNode[T]], res: String, rest: List[TreeNode[T]]): String = (tn, rest) match {
      case (None, Nil) => res
      case (Some(n), _) => acc(n.leftChild, res, n :: rest)
      // Eliminate the case bellow by using flatMap and r.toList bellow
      //case (None, TreeNode(v, _, None) :: xs) => acc(None, res + sep + v.toString, xs)
      case (None, TreeNode(v, _, r) :: xs) => acc(r flatMap (_.leftChild), res + sep + v.toString, r.toList ::: xs)
    }
    // Remove the first sep 
    acc(Option(this), "", List()).substring(sep.length)
  }
}

// Examples
class BinarySearchTrees
object BinarySearchTrees {

  def main(args: Array[String]) {

    val bst = TreeNode(5,
      Option(TreeNode(3,
        Option(TreeNode(2,
          Option(TreeNode(1, None, None)), None)),
        Option(TreeNode(4, None, None)))),
      Option(TreeNode(7,
        Option(TreeNode(6, None, None)),
        Option(TreeNode(9,
          Option(TreeNode(8, None, None)), None)))))

    val bst2 = TreeNode(5, Option(TreeNode(3, None, None)), None)

    println(bst2.mkList)
    println(bst.mkList)

    // Then we can use the list to print
    println(bst.mkList.mkString(", "))

    println
    println(bst.mkString())
    println(bst.mkStringTR(" ~ "))

    println
    println(bst2.mkString())
    println(bst2.mkStringTR())
  }

}