Binary tree generation

gistfile1.scala

// Can it really be this hard???

sealed trait BinTree
case class Node(left: BinTree, right: BinTree) extends BinTree
case class Leaf(n: Int) extends BinTree

def generateTree(ints: Iterable[Int]): BinTree = {
      type BinTreePair = (BinTree, BinTree)
  
  def pairOffTrees(trees: List[BinTree]): List[BinTreePair] = {
    @tailrec
    def pair(treesLeft: List[BinTree], 
             pairsSoFar: List[BinTreePair]): List[BinTreePair] = treesLeft match {
      
      case a :: b :: rest => pair(rest, (a,b) :: pairsSoFar)
      case _ => pairsSoFar
    }
    pair(trees, Nil)
  }
  
  def buildTrees(trees: List[BinTree]): List[BinTree] = {
    @tailrec
    def joinPairs(pairsLeft: List[BinTreePair], 
               treesSoFar: List[BinTree]): List[BinTree] = pairsLeft match {
      case Nil => treesSoFar
      case (a,b) :: rest => joinPairs(rest, Node(a,b) :: treesSoFar)
    }
    joinPairs(pairOffTrees(trees), Nil)
  }

  @tailrec
  def reduceTrees(trees: List[BinTree]): BinTree = trees match {
    case Nil => Leaf(0)
    case t :: Nil => t
    case _ => reduceTrees(buildTrees(trees))
  }

  val leaves = ints.toList map Leaf.apply
  reduceTrees(leaves)
}