Lazy tree traversal iterator in Scala

Question

If my tree is defined as such:

case class Node(value: Int, children: Seq[Node])

but for the sake of the argument, let's say that accessing the children are expensive such that I want to traverse them only when I actuall need to.

If a non-strict, eager DFS traversal on Node is defined as

def traverse(node: Node): Unit = {
  node.children foreach { child => traverse(child) }
}

How do I create a lazy counterpart of it?

Ideally I will have an iterator method which returns an iterator based on DFS traversal ordering that only evaluates the next element when next() is called on it:

val tree = Node(1, Seq(Node(2, Nil), Node(3, Nil)))
val dfsIt = tree.iterator // get a iterator with a DFS traversal ordering
val nextNode = dfsIt.next() // compute which element to return on demand

Answer 1

case class Node(value: Int, children: Seq[Node]) {

  def dfsIterator: Iterator[Node] = {
    println(value)
    children.iterator.map(_.dfsIterator).flatten ++ Iterator(this)
  }
}