binaryTree.scala

object BT {
  case class BNode(v: Int, l: Option[BNode], r: Option[BNode])

  val bt = BNode(5,
    Some(BNode(4, Some(BNode(3, None, None)), None)),
    Some(BNode(10, None,
      Some(BNode(15, None, None)))))

  def bt2Sorted(bt: BNode, l: List[Int] = List[Int]()): List[Int] = {
    bt match {
      case BNode(i, Some(lbt), Some(rbt)) => bt2Sorted(lbt) ++ l ++ List(i) ++ bt2Sorted(rbt)
      case BNode(i, Some(lbt), None) => bt2Sorted(lbt) ++ l ++ List(i)
      case BNode(i, _, Some(rbt)) => l ++ List(i) ++ bt2Sorted(rbt)
      case BNode(i, None, None) => i :: l
    }
  }

  assert(bt2Sorted(bt) == List(3,4,5,10, 15))
}