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_03_InorderTraversal_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]

  // in-order traversal
  def inorder[A](tree: BinTree[A]): List[A] = tree match {
    case Empty =>
      Nil
    case Node(v, l, r) =>
      inorder(l) ::: (v :: inorder(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(inorder(tree))

}