InvertTree.sc

InvertTree.sc

sealed trait Tree[+A]
case object EmptyTree extends Tree[Nothing] {
    override def toString = "nil"
}
case class Node[A] (l: Tree[A], v: A, r: Tree[A]) extends Tree[A] 

object Tree {
  def empty[A]: Tree[A] = EmptyTree
  def node[A](value: A, left: Tree[A] = empty, right: Tree[A] = empty): Tree[A]
    = Node(left, value, right)
}

import Tree._
val t1 = node(4,
                    node(2
                      , node(1)
                      , node(3)
                    ) , 
                    node(7
                      , node(6)
                      , node(9)
                    )
          )
          
pprint.log(t1)
pprint.pprintln(t1)

def treeFold[A, B](t: Tree[A], z: B) (f: (B, A, B) => B) : B =  {
  // alias 
  def treeFoldAux(t: Tree[A])= treeFold(t, z)(f)

  t match {
    case EmptyTree => z 
    case Node(l, a, r) => f (treeFoldAux(l), a, treeFoldAux(r)) 
  }

}

def size[T] (tree: Tree[T]) =
  treeFold(tree, 0: Int){(l,x,r) => l + r + 1}

pprint.log(size(t1))

val t1String = 
  treeFold(t1, Tree.empty[String]) { (l, a, r)
    => Tree.node(a.toString, l,  r)
  }

pprint.log(t1String)



// map 

def map[A, B] (tree: Tree[A]) (f: A => B) : Tree[B] = 
  treeFold(tree, Tree.empty[B]) { (l , a, r ) => Tree.node(f(a), l, r) }



pprint.log(map(t1) ((a: Int) => a * 1000) )



def invertTree[A](tree: Tree[A]): Tree[A] = 
  treeFold(tree, Tree.empty[A]) {(left, a, right) => Tree.node(a, right, left)}


  pprint.log(invertTree(t1))
    pprint.log(invertTree(t1))