Benchmark for comparing between Iterator and Stream. Because StreamIterator has bug, I created fixed version of StreamIterator.

BinTreeIteratorBenchmark.scala

object BinTreeIteratorBenchmark {
  final class BugFixedStreamIterator[A] (private[this] var self: Stream[A]) extends Iterator[A] {
    // A call-by-need cell.
    class LazyCell(st: => Stream[A]) {
      lazy val v = st
    }

    private var these = {
      val stream = self
      val result = new LazyCell(stream)
      self = null
      result
    }

    def hasNext: Boolean = these.v.nonEmpty
    def next: A = if (isEmpty) Iterator.empty.next else {
      val cur    = these.v
      val result = cur.head
      these = new LazyCell(cur.tail)
      result
    }
    override def toStream = {
      val result = these.v
      these = new LazyCell(Stream.empty)
      result
    }
    override def toList = toStream.toList

  }

  sealed trait Tree
  case class Node(v: Int, l: Tree, r: Tree) extends Tree
  case object Leaf extends Tree

  def toIterator(node: Tree): Iterator[Int] = {
    def toStream(n: Tree): Stream[Int] = n match {
      case Node(v, l, r) => v #:: toStream(l) #::: toStream(r)
      case Leaf => Stream.empty
    }
    new BugFixedStreamIterator(toStream(node))
  }
  
  def toIteratorImperative(node: Tree): Iterator[Int] = {
    new Iterator[Int] {
      import collection.mutable.Stack
      private val stack = Stack.empty[(Node, Boolean)]
      node match {
        case n: Node => stack.push(n -> false)
        case _ =>
      }

      override def hasNext = stack.nonEmpty
      override def next = {
        if (!hasNext)
          throw new NoSuchElementException("next on empty iterator")
        else stack.pop match {
          case (n, false) =>
            stack.push(n -> true)
            n.l match {
              case l : Node => stack.push(l -> false)
              case _ =>
            }
            next
          case (n, true) =>
            n.r match {
              case r: Node => stack.push(r -> false)
              case _ =>
            }
            n.v
        }
      }
    }
  }

  val uniqueId = Iterator.from(1)
  def createTree(depth: Int): Tree = {
    if (depth == 0) Leaf
    else {
      val l = createTree(depth - 1)
      val v = uniqueId.next
      val r = createTree(depth - 1)
      Node(v, l, r)
    }
  }

  def main(args: Array[String]) {
    println("create tree")
    val tree = createTree(20)
    
    println("traverse tree (imperative)")
    var it = toIteratorImperative(tree)
    for(e <- it if e % 10000 == 0) {
      println(e)
    }
    
    println("traverse tree (Stream)")
    it = toIterator(tree)
    for(e <- it if e % 10000 == 0) {
      println(e)
    }
  }
}