binaryTree.scala

// data type
sealed abstract class Tree {
  def foldLeft[B](z: B)(f: (B, Int) => B): B
}
case class Branch(value: Int, left: Tree, right: Tree) extends Tree {
  def foldLeft[B](z: B)(f: (B, Int) => B): B =
    right.foldLeft(f(left.foldLeft(z)(f), value))(f)
}
case object Empty extends Tree {
  def foldLeft[B](z: B)(f: (B, Int) => B): B = z
}

// sort
def sort(tree: Tree): Tree = {
  def insert(h: Int, res: Tree): Tree = res match{
    case Empty => Branch(h, Empty, Empty)
    case Branch(v, l, r) =>
      if (h < v)
        Branch(v, insert(h, l), r)
      else if(h > v)
        Branch(v, l, insert(h, r))
      else
        Branch(h, Branch(v, l, r), Empty)
  }

  def func(tr: Tree, acc: Tree): Tree = tr match {
    case Empty => acc
    case Branch(v, l, r) => func(r, insert(v, func(l, acc)))
  }

  func(tree, Empty)
}

//example
val tree: Tree = Branch(1, Branch(2, Empty, Empty), Branch(3, Empty, Empty))

tree.foldLeft(Empty)(sort)