Veerapat Boonvanich Veerapat Boonvanich - 2 months ago 19
Scala Question

How to covert List to Tree without stack overflow

I have a problem with List[(nodeID, parentID)] -> Tree structure

val tree: List[(Int, Int)] = List((1,0),(2,0),(3,0),(4,1),(5,4),(6,2),(7,6))


my tree case class

case class Tree(value: Int, subTree: List[Tree])


my code

def DFS(tree: List[(Int, Int)], id: Int): List[Tree] = {
if(tree.isEmpty) Nil
else List(Tree(id, tree.filter(x => x._2 == id).flatMap(x => DFS(tree, x._1))))}


result

List(Tree(0,List(Tree(1,List(Tree(4,List(Tree(5,List()))))), Tree(2,List(Tree(6,List(Tree(7,List()))))), Tree(3,List()))))


and I found stack overflow for large data in list

so I want to change it to tail-recursive, map or fold

Answer

There is a lot to improve from performance point of view, but it seems to work:

val tree: List[(Int, Int)] = List((1,0),(2,0),(3,0),(4,1),(5,4),(6,2),(7,6))
case class Tree(value: Int, subTree: List[Tree])

// Sort in reverse BFS order
@annotation.tailrec
def BFS(tree: List[(Int, Int)], ids: List[(Int, Int)], acc: List[(Int, Int)]): List[(Int, Int)] = {
  ids match {
    case Nil => acc
    case head::tail =>
      BFS(tree, tail ++ tree.filter(_._2 == head._1), head::acc) 
  }
}

// acc: List of (parent, Tree)
@annotation.tailrec
def fold(bfs: List[(Int, Int)], acc: List[(Int, Tree)]): List[(Int, Tree)] = {
  bfs match {
    case Nil => acc
    case head::tail =>
      val (l, r) = acc.partition(_._1 == head._1)
      fold(tail, (head._2, Tree(head._1, l.map(_._2))) :: r)
  }
}

fold(BFS(tree, List((0, 0)), Nil), Nil).map(_._2)
Comments