CODEWITHSUNDEEP
scala
zella
zella

Reputation: 4685

How to implement tree traversal with tail recusrion

I wrote simple traversal function:

case class Node(data: String, childs: Seq[Node] = Seq.empty)

def travers(root: Node, visit: String => Unit): Unit = {

  def recur(n: Node): Unit = {
    visit(n.data)
    for (c <- n.childs) recur(c)
  }

  recur(root)
}

val root = Node("1",
           Seq(Node("2",
               Seq(Node("3"), Node("4")))))

travers(root, s => println(s))

How to implement it with tail recursion?

Upvotes: 1

Views: 142

Answers (2)

Tzach Zohar
Tzach Zohar

Reputation: 37832

You can try changing the recursion to handle a sequence of children at each iteration - and get a breadth-first traversal (unlike the depth-first order @JoeK's answer and your implementation share):

def travers(root: Node, visit: String => Unit): Unit = {
  @tailrec
  def recur(ns: List[Node]): Unit = {
    ns.foreach(n => visit(n.data))
    ns.flatMap(_.childs) match {
      case Nil => // done
      case more => recur(more)
    }
  }
  recur(List(root))
}

Upvotes: 2

Joe K
Joe K

Reputation: 18424

You could do this by "manually" managing a stack of nodes to visit, like this:

def travers(root: Node, visit: String => Unit): Unit = {

  @scala.annotation.tailrec
  def recur(stack: List[Node]): Unit = stack match {
    case Node(d, children) :: rest => {
      visit(d)
      recur(children.toList ++ rest)
    }
    case Nil => {}
  }

  recur(List(root))
}

Upvotes: 3

Related Questions