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

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
}
}

// 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