toTree

toTree.scala

def toTree(ls: List[Int]): IntSet = {
  def toTreeAux(ls: List[Int], n: Int): (List[Int], IntSet) = {
    if (n <= 0)
      (ls, Empty)
    else {
      val (lls, lt) = toTreeAux(ls, n / 2) // construct left sub-tree
      val x :: xs = lls // extract root node
      val (xr, rt) = toTreeAux(xs, n - n / 2 - 1) // construct right sub-tree 

      (xr, IntSet(x, lt, rt)) // construct tree
    }
  }
  val (ls_1, tree) = toTreeAux(ls, List.length(ls))
  tree
}