Tree traversal comparison: stream vs explicit state stack

BinTreeIterator.scala

object BinTreeIterator {
  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
    }
    toStream(node).iterator
  }
  
  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)
    }
  }
}