[rybosome]

This is why I love pattern matching in languages that support it - typing is just one of the things on which they can switch. As the Scala website puts it (paraphrasing), "Pattern matching is switch on steroids!"

Here is how you would return all leaf values in a binary tree in Scala:

    case class Node
    case class Fork(left: Node, right: Node) extends Node
    case class Leaf(value: Int) extends Node

    def getValues(node: Node): List[Int] = node match {
    	    case f: Fork => getValues(f.left) ++ getValues(f.right)
	    case l: Leaf => List(l.value)
    }

EDIT: Would actually be more idiomatic in Scala to extract the values from the case classes rather than just matching on type...yet another wonderful feature of pattern matching. Coded as follows:

    def getValues(node: Node): List[Int] = node match {
	    case Fork(left, right) => getValues(left) ++ getValues(right)
	    case Leaf(value) => List(value)
    }

[rybosome]

Here's the tail-call optimized version, won't blow the stack. Technically idiomatic, but way too cryptic to be serious code. Clearly I need more outlets for writing Scala. =)

    @tailrec
    def getValuesFromNode(node: Node, accValues: List.empty[Int], nodeList: List.empty[Node]): List[Int] = node match {
      case Fork(left, right) => getValuesFromList(accValues, nodeList ++ List(left, right))
      case Leaf(value) => getValuesFromList(accValues ++ List(value), nodeList)
    }

    @tailrec
    def getValuesFromList(accValues: List.empty[Int], nodeList: List.empty[Node]): List[Int] = nodeList match {
      case x :: xs => getValuesFromNode(x, accValues, xs)
      case _ => accValues
    }