Tree.scala

/**
 * D Holbrook
 *
 * Code Club: PO1
 *
 * (*) Define a binary tree data structure and related fundamental operations.
 *
 * Use whichever language features are the best fit (this will depend on the language you have selected).  The following operations should be supported:
 *
 *    Constructors
 *        (bitree data left right) - Should return a binary tree containing data and the left and right children.
 *    Accessors
 *        (bitree-data t) - Should return the data contained by the tree.
 *        (bitree-left t) - Should return the left child of the tree.
 *        (bitree-right t) - Should return the right child of the tree.
 *    Predicates
 *        (bitree-leaf? t) - Should return true if the tree is a leaf (has null left and right children), false otherwise
 */
trait Tree[+A] {

  import scala.annotation.tailrec

  def value: Option[A] = this match {
    case n: Node[A] => Some(n.v)
    case l: Leaf[A] => Some(l.v)
    case Empty      => None
  }

  def left: Option[Tree[A]] = this match {
    case n: Node[A] => Some(n.l)
    case l: Leaf[A] => None
    case Empty      => None
  }

  def right: Option[Tree[A]] = this match {
    case n: Node[A] => Some(n.r)
    case l: Leaf[A] => None
    case Empty      => None
  }

  /**
   * Represents a deferred evaluation of a node value
   */
  private case class Eval[A](v: A) extends Tree[A]

  /**
   * represents common functionality of all traversal order folds
   */
  @tailrec
  private def foldLoop[A, B](a: List[Tree[A]], z: B)(f: (B, A) => B)(o: (Node[A], List[Tree[A]]) => List[Tree[A]]): B = a match {
    case (n: Node[A]) :: tl => foldLoop(o(n, tl), z)(f)(o) // never directly evaluate nodes, function o will create new accumulator
    case (l: Leaf[A]) :: tl => foldLoop(tl, f(z, l.v))(f)(o) // always evaluate Leaf 
    case (e: Eval[A]) :: tl => foldLoop(tl, f(z, e.v))(f)(o) // always evaluate Eval 
    case Empty :: tl        => foldLoop(tl, z)(f)(o) // ignore Empty
    case _                  => z // will be Nil (empty list)
  }

  /**
   * fold with preorder traversal (root, left, right)
   * Tail Recursive Optimized
   *
   *        F
   *      /   \
   *    B       G
   *   / \       \
   *  A   D       I
   *     / \     /
   *    C   E   H
   *
   * head evaluate accumulator
   * ---- -------- -----------
   *              | (F)
   * F   | ()     | F::B::G::()
   * F   | (F)    | (B,G)
   * B   | ()     | B::A::D::(G)
   * B   | (B)    | (A,D,G)
   * A   | (A)    | (D,G)
   * D   | ()     | D::C::E::(G)
   * D   | (D)    | (C,E,G)
   * C   | (C)    | (E,G)
   * E   | (E)    | (G)
   * G   | ()     | G::I::()
   * G   | (G)    | (I)
   * I   | ()     | I::H::()
   * I   | (I)    | (H)
   * H   | (H)    | ()
   *
   * result
   * F, B, A, D, C, E, G, I, H
   */
  def foldPreorder[B](z: B)(f: (B, A) => B): B = {
    foldLoop(List(this), z)(f) { (n, tl) => Eval(n.v) :: n.l :: n.r :: tl }
  }

  /**
   * fold with inorder traversal (left, root, right)
   * tail recursive optimized
   *
   *        F
   *      /   \
   *    B       G
   *   / \       \
   *  A   D       I
   *     / \     /
   *    C   E   H
   *
   * head evaluate accumulator
   * ---- -------- -----------
   *              | (F)
   * F   | ()     | B::F::G::()
   * B   | ()     | A::B::D::(F,G)
   * A   | (A)    | (B,D,F,G)
   * B   | (B)    | (D,F,G)
   * D   | ()     | C::D::E::(F,G)
   * C   | (C)    | (D,E,F,G)
   * D   | (D)    | (E,F,G)
   * E   | (E)    | (F,G)
   * F   | (F)    | (G)
   * G   | ()     | G::I::()
   * G   | (G)    | (I)
   * I   | ()     | H::I::()
   * H   | (H)    | H
   * I   | (I)    | ()
   *
   * result
   * A,B,C,D,E,F,G,H,I
   */
  def foldInorder[B](z: B)(f: (B, A) => B): B = {
    foldLoop(List(this), z)(f) { (n, tl) => n.l :: Eval(n.v) :: n.r :: tl }
  }

  /**
   * fold with postorder traversal (left, right, root)
   * tail recursive optimized
   *
   *        F
   *      /   \
   *    B       G
   *   / \       \
   *  A   D       I
   *     / \     /
   *    C   E   H
   *
   * head evaluate accumulator
   * ---- -------- -----------
   *              | (F)
   * F   | ()     | B::G::F::()
   * B   | ()     | A::D::(B,G,F)
   * A   | (A)    | (D,B,G,F)
   * D   | ()     | C::E::D::(B,G,F)
   * C   | (C)    | (E,D,B,G,F)
   * E   | (E)    | (D,B,G,F)
   * D   | (D)    | (B,G,F)
   * B   | (B)    | (G,F)
   * G   | ()     | I::G::(F)
   * I   | ()     | H::I::(G,F)
   * H   | (H)    | (I,G,F)
   * I   | (I)    | (G,F)
   * G   | (G)    | (F)
   * F   | (F)    | ()
   *
   * result
   * A,C,E,D,B,H,I,G,F
   */
  def foldPostorder[B](z: B)(f: (B, A) => B): B = {
    foldLoop(List(this), z)(f) { (n, tl) => n.l :: n.r :: Eval(n.v) :: tl }
  }

  /**
   * fold with levelorder traversal
   * tail recursive optimized
   *
   *        F
   *      /   \
   *    B       G
   *   / \       \
   *  A   D       I
   *     / \     /
   *    C   E   H
   *
   * head evaluate accumulator
   * ---- -------- -----------
   *              | (F)
   * F   | ()     | (F::()) ::: (B,G)
   * F   | (F)    | (B,G)
   * B   | ()     | (B::(G)) ::: (A,D)
   * B   | (B)    | (G,A,D)
   * G   | ()     | (G::(A,D)) ::: (I)
   * G   | (G)    | (A,D,I)
   * A   | (A)    | (D,I)
   * D   | ()     | (D::(I)) ::: (C,E)
   * D   | (D)    | (I,C,E)
   * I   | ()     | (I::(C,E)) ::: (H)
   * I   | (I)    | (C,E,H)
   * C   | (C)    | (E,H)
   * E   | (E)    | (H)
   * H   | (H)    | ()
   *
   * result
   * F, B, G, A, D, I, C, E, H
   */
  def foldLevelorder[B](z: B)(f: (B, A) => B): B = {
    foldLoop(List(this), z)(f) { (n, tl) => (Eval(n.v) :: tl) ::: List(n.l, n.r) }
  }

  /**
   * calls foldInorder
   */
  def fold[B](z: B)(f: (B, A) => B): B = foldInorder(z)(f)

  /**
   * P02
   * (*) Count the number of nodes in a binary tree.
   */
  def size: Int = fold(0) { (sum, v) => sum + 1 }

  /**
   * P03
   * (*) Determine the height of a binary tree.
   * Definition:  The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero.
   */
  def height: Int = {
    def loop(t: Tree[A]): Int = t match {
      case l: Leaf[A] => 1
      case n: Node[A] => Seq(loop(n.left.get), loop(n.right.get)).max + 1
      case _          => 0
    }
    loop(this) - 1
  }

  /**
   * P04
   * (*) Count the number of leaves in a binary tree.
   */
  def leafCount: Int = {
    @tailrec
    def loop(t: List[Tree[A]], z: Int): Int = t match {
      case (l: Leaf[A]) :: tl => loop(tl, z + 1)
      case (n: Node[A]) :: tl => loop(n.left.get :: n.right.get :: tl, z)
      case _ :: tl            => loop(tl, z)
      case _                  => z
    }
    loop(List(this), 0)
  }

  def toSeq: Seq[A] = fold(List[A]()) { (l, v) => v :: l } reverse

  def toSeqPreorder: Seq[A] = foldPreorder(List[A]()) { (l, v) => v :: l } reverse
  def toSeqInorder: Seq[A] = foldInorder(List[A]()) { (l, v) => v :: l } reverse
  def toSeqPostorder: Seq[A] = foldPostorder(List[A]()) { (l, v) => v :: l } reverse
  def toSeqLevelorder: Seq[A] = foldLevelorder(List[A]()) { (l, v) => v :: l } reverse

  /**
   * P05
   * (**) Find the last element in a binary tree using pre/in/post/level order traversals.
   *  Note:  This is S-99 problem P01 converted from lists to binary trees.
   */
  def lastPreorder = toSeqPreorder.last
  def lastInorder = toSeqInorder.last
  def lastPostorder = toSeqPostorder.last
  def lastLevelorder = toSeqLevelorder.last

  /**
   * P06
   * (**) Find the last but one element in a binary tree using pre/in/post/level order traversals.
   *  Note:  This is S-99 problem P02 converted from lists to binary trees.
   */
  def penultimatePreorder = toSeqPreorder.dropRight(1).last
  def penultimateInorder = toSeqInorder.dropRight(1).last
  def penultimatePostorder = toSeqPostorder.dropRight(1).last
  def penultimateLevelorder = toSeqLevelorder.dropRight(1).last

  /**
   * P07
   * (**) Find the Nth element in a binary tree using pre/in/post/level order traversals.
   * By convention, the first element in the tree is element 0.
   *
   */
  def nthPreorder(n: Int) = toSeqPreorder(n)
  def nthInorder(n: Int) = toSeqInorder(n)
  def nthPostorder(n: Int) = toSeqPostorder(n)
  def nthLevelorder(n: Int) = toSeqLevelorder(n)

}

case class Node[A](v: A, l: Tree[A], r: Tree[A]) extends Tree[A]
case class Leaf[A](v: A) extends Tree[A]
case object Empty extends Tree[Nothing]

object Run extends App {
  val t: Tree[Symbol] = Node('F, Node('B, Leaf('A), Node('D, Leaf('C), Leaf('E))), Node('G, Empty, Node('I, Leaf('H), Empty)))
  println("tree: " + t)

  //print the value of b node navigating from root
  for {
    b <- t.left
    value <- b.value
  } println("B node: " + value)

  //print the value of e node navigating from root
  for {
    b <- t.left
    d <- b.right
    value <- d.value
  } println("D node: " + value)

  //no println() is executed for empty node chain
  for {
    b <- t.left
    d <- b.right
    e <- d.right
    x <- e.right
    value <- x.value
  } println("X node SHOUL NOT PRINT!: " + value)

  println("as seq: " + t.toSeq)

  println("count: " + t.size)
  assert(t.size == 9)

  println("height: " + t.height)
  assert(t.height == 3)

  println("leaft count: " + t.leafCount)
  assert(t.leafCount == 4)

  println("as seqPreorder: " + t.toSeqPreorder)
  println("as seqInorder: " + t.toSeqInorder)
  println("as seqPostorder: " + t.toSeqPostorder)
  println("as seqLevelorder: " + t.toSeqLevelorder)

  println("last preorder :" + t.lastPreorder)
  println("last inorder :" + t.lastInorder)
  println("last postorder :" + t.lastPostorder)
  println("last levelorder: " + t.lastLevelorder)

  println("nth preorder 5 : " + t.nthPreorder(5))
  println("nth inorder 5 : " + t.nthInorder(5))
  println("nth postorder 5 : " + t.nthPostorder(5))
  println("nth levelorder 5 : " + t.nthLevelorder(5))

  //    
  /**
   * **** output *********
   *
   * tree: Node('F,Node('B,Leaf('A),Node('D,Leaf('C),Leaf('E))),Node('G,Empty,Node('I,Leaf('H),Empty)))
   * B node: 'B
   * D node: 'D
   * as seq: List('A, 'B, 'C, 'D, 'E, 'F, 'G, 'H, 'I)
   * count: 9
   * height: 3
   * leaft count: 4
   * as seqPreorder: List('F, 'B, 'A, 'D, 'C, 'E, 'G, 'I, 'H)
   * as seqInorder: List('A, 'B, 'C, 'D, 'E, 'F, 'G, 'H, 'I)
   * as seqPostorder: List('A, 'C, 'E, 'D, 'B, 'H, 'I, 'G, 'F)
   * as seqLevelorder: List('F, 'B, 'G, 'A, 'D, 'I, 'C, 'E, 'H)
   * last preorder :'H
   * last inorder :'I
   * last postorder :'F
   * last levelorder: List('F, 'B, 'G, 'A, 'D, 'I, 'C, 'E, 'H)
   * nth preorder 5 : 'C
   * nth inorder 5 : 'E
   * nth postorder 5 : 'B
   * nth levelorder 5 : 'D
   *
   * ***********************
   */

}