import scala.annotation.tailrec


abstract class BST[T]{
    def _doprint(tier:Int)
};
case class Branch[T](root:T,lst:BST[T],rst:BST[T]) extends BST[T] {
    def indent(tier:Int):String = {
        @tailrec def spaces (rem : Int, acc : String):String = {
            rem match{
                case 0 => acc
                case _ => spaces(rem-1, acc+" ")
            }
        }
        spaces(tier,"")
    }
    override def _doprint(tier:Int) = {
        print(indent(tier)) ;
        lst match{
            case Empty() =>
                rst match{
                    case Empty() => print("|") ; println(root)
                    case _ => print("\\") ; println(root) ; rst._doprint(tier+1)
                }
            case _ => print("\\") ; println(root) ; lst._doprint(tier+1) ; rst._doprint(tier+1)
        }
    }
};
case class Empty[T] () extends BST[T] {
    override def _doprint(tier:Int) = {
        println("[]")
    }
};

object BSTOps {
    def newEmptyBST[T]():Empty[T] = {
        Empty[T]()
    };
    def newBSTFromLeaf[T](lf:T):Branch[T] = {
        Branch[T](lf,newEmptyBST(),newEmptyBST())
    };
    def newBSTFromSubBSTs[T](root:T,lst:BST[T],rst:BST[T]):Branch[T] = {
        Branch(root,lst,rst)
    };
    def printBST[T](t:BST[T]) = {
        t._doprint(0)
    };
    def foldl[T,ACC](fun : (T, ACC) => ACC, acc: ACC, t:BST[T]):ACC = {
        t match {
            case Empty() => acc
            case Branch(r,lst,rst) =>
                foldl(
                    fun,
                    foldl(
                        fun,
                        fun(r,acc),
                        lst
                    ),
                    rst
                )
        }
    };
    def exampleTree():BST[Int] = {
        val bstOps = BSTOps
        bstOps.newBSTFromSubBSTs(
            1,
            bstOps.newEmptyBST[Int](),
            bstOps.newBSTFromSubBSTs(
                2,
                bstOps.newBSTFromSubBSTs(
                    3,
                    bstOps.newEmptyBST[Int](),
                    bstOps.newEmptyBST[Int]()
                ),
                bstOps.newBSTFromSubBSTs(
                    4,
                    bstOps.newEmptyBST[Int](),
                    bstOps.newEmptyBST[Int]()
                )
            )
        )
    };
};

object Main extends App {
    val bstOps = BSTOps
    bstOps.printBST(bstOps.exampleTree())
    println("sum="+bstOps.foldl[Int,Int]((a:Int,b:Int)=>a+b,0,bstOps.exampleTree()))
}