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_01_SimpleTreeAlgorithms_App extends App {

  sealed trait BinTree
  case object Empty extends BinTree
  case class Node(value:  Int,
                  left:   BinTree,
                  right:  BinTree
                 ) extends BinTree

  def Sum(binTree: BinTree): Int = binTree match {
    case Empty => 0
    case Node(v, l, r) => Sum(l) + Sum(r) + v
  }

  def Depth(binTree: BinTree): Int = binTree match {
    case Empty => 0
    case Node(_, l, r) => Math.max(Depth(l), Depth(r)) + 1
  }

  def ToBTree(lst: List[Int]): BinTree = lst match {
    case Nil => Empty
    case x0 :: Nil => Node(x0, Empty, Empty)
    case x0 :: x1 :: Nil =>
      Node(x0, Node(x1, Empty, Empty), Empty)
    case _ =>
      Node(lst(0), ToBTree(lst.slice(1, lst.length/2)), ToBTree(lst.slice(lst.length/2, lst.length)))
  }


  val tree: BinTree =
    Node(1,
      Node(2,
        Empty, Empty),
      Node(3,
        Node(6, Empty, Empty),
        Empty
      )
    )

  println(Sum(tree))
  println(Depth(tree))

  println(ToBTree(List(1,2,3,4,5,6)))

}