TreeTraversal.scala

// Implementation of Tree Traversal in Scala

package kata

trait Node {
  def postorder: Stream[Node]
  def inorder: Stream[Node]
  def preorder: Stream[Node]
}

case object Empty extends Node {
  override def preorder: Stream[Node] = Stream(this)
  override def inorder: Stream[Node] = Stream(this)
  override def postorder: Stream[Node] = Stream(this)
}

case class Tree(value: Int, left: Node, right: Node) extends Node {
  override def preorder: Stream[Node] = 
    Stream(this) #::: left.preorder #::: right.preorder

  override def inorder: Stream[Node] =
    left.inorder #::: Stream(this) #::: right.inorder

  override def postorder: Stream[Node] =
    left.postorder #::: right.postorder #::: Stream(this.asInstanceOf[Node])
}