package kapitel_05

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 5, Bäume: Immer einer über den anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_05_02_PreorderTraversal_App extends App {

  sealed trait BinTree[+T]
  case object Empty extends BinTree[Nothing]
  case class Node[+A](
                       value:  A,
                       left:   BinTree[A],
                       right:  BinTree[A]
                     ) extends BinTree[A]

  // pre-order traversal
  def preorder[A](tree: BinTree[A]): List[A] = tree match {
    case Empty =>
      Nil
    case Node(v, l, r) =>
      v :: preorder(l) ::: preorder(r)
  }

  val tree: BinTree[Int] =
    Node(1,
      Node(2,
        Empty, Empty),
      Node(3,
        Node(4, Empty, Empty),
        Node(5,
          Node(6, Empty, Node(7, Empty, Empty)),
          Node(8, Empty, Node(9, Empty, Empty)))
      )
    )

  println(preorder(tree))

}