tree.scala

case class Node(level: Int, value: String, children: List[Node])

// This returns a pair of lists, which of the first one is the result, 
// and given the constraints on the input, must always have only one element.
// The second list must always be empty in the end result.
def build(input: List[(Int, String)]): (List[Node], List[Node]) = 
  input match {
    case Nil => (Nil, Nil)
    case (level, value)::Nil => (List(Node(level, value, List())), Nil)
    case (level, value)::tail =>
      val (next, stash) = build(tail)
      if (level < next.head.level) 
        (Node(level, value, next)::stash.takeWhile(_.level == level), stash.dropWhile(_.level == level))
      else if (level == next.head.level) 
      	(Node(level, value, List())::next, stash)
      else 
	(List(Node(level, value, List())), next ++ stash)
  }