Scala binary tree

Tree.scala

trait Tree[+A] {

  private implicit def preorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
    fold(n.r, fold(n.l, f(z, n.v))(f)(preorder))(f)(preorder)
  }

  private def inorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
    fold(n.r, f(fold(n.l, z)(f)(inorder), n.v))(f)(inorder)
  }

  private def postorder[A, B](n: Node[A], z: B, f: (B, A) => B): B = {
    f(fold(n.r, fold(n.l, z)(f)(postorder))(f)(postorder), n.v)
  }

  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
  }

  def fold[B](z: B)(f: (B, A) => B): B = {
    fold(this, z)(f)
  }

  private def fold[A, B](t: Tree[A], z: B)(f: (B, A) => B)(implicit o: (Node[A], B, (B, A) => B) => B): B = t match {
    case l: Leaf[A] => f(z, l.v)
    case n: Node[A] => o(n, z, f)
    case _          => z
  }

  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
  }

  def leafCount: 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)).sum
      case _          => 0
    }
    loop(this)
  }

  def size: Int = fold(0) { (sum, v) => sum + 1 }

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

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

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

  def toSeqPostorder: Seq[A] = fold(this, List[A]()) { (l, v) => v :: l }(postorder) reverse
  
  def lastPreorder = toSeqPreorder.last
  
  def lastInorder = toSeqInorder.last
  
  def lastPostorder = toSeqPostorder.last

  def penultimatePreorder = toSeqPreorder.dropRight(1).last
  
}

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('A, Node('B, Leaf('D), Leaf('E)), Node('C, Empty, Node('F, Leaf('G), 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
    e <- b.right
    value <- e.value
  } println("E node: " + value)

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

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

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

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

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

  println("last preorder :" + t.lastPreorder)
  assert(t.lastPreorder == 'G)
 
  println("last inorder :" + t.lastInorder)
  assert(t.lastInorder == 'F)
  
  println("last postorder :" + t.lastPostorder)
  assert(t.lastPostorder == 'A)  
  
  println("penultimate preorder :" + t.penultimatePreorder)  
    
  /**
   * **** output *********
   *
    tree: Node('A,Node('B,Leaf('D),Leaf('E)),Node('C,Empty,Node('F,Leaf('G),Empty)))
    B node: 'B
    E node: 'E
    count: 7
    height: 3
    leaft count: 3
    as seq: List('A, 'B, 'D, 'E, 'C, 'F, 'G)
    last preorder :'G
    last inorder :'F
    last postorder :'A
    penultimate preorder :'F

   * ***********************
   */

}

Beautiful.

🎉

Would some one please show my how to use foldLoop or fold to return a modified tree?

Good job!

Exquisite.

very cool, nice work :)