CODEWITHSUNDEEP
scala
Kity Cartman
Kity Cartman

Reputation: 895

Modifying Node tree in Scala

enter image description here

I have a node tree:

val root = Node("a", List(Node("w", Nil), Node("b", List(Node("c", List(Node("d", Nil))), Node("m", List(Node("n", Nil)))))))

and list of intermediate nodes:

val ks = List("b", "m")

that leads me to where which I have to add a node:

val child = Node("t", Nil)

that results in:

val res = Node("a", List(Node("w", Nil), Node("b", List(Node("c", List(Node("d", Nil))), Node("m", List(Node("n", Nil), Node("t", Nil)))))))

Tree in Scala is modeled as:

sealed trait Tree[A]

case class Empty[A]() extends Tree[A]

case class Node[A](rootNode: A, subtree: List[Tree[A]]) extends Tree[A]

I have made an attempt to traverse the tree and add the node like so,

@tailrec
def traverseAndAdd(root: Node[String], subNode: Node[String], child: Node[String], ls: List[String]): Node[String] = ls match {
  case Nil =>
    root
  case x :: Nil =>
    val k = subNode.subtree.filter(l => l.asInstanceOf[Node[String]].rootNode == x).head.asInstanceOf[Node[String]].subtree :+ child
    println(k)
    traverseAndAdd(root, subNode, child, Nil)
  case x :: xs =>
    traverseAndAdd(root, subNode.subtree.filter(l => l.asInstanceOf[Node[String]].rootNode == x).head.asInstanceOf[Node[String]], child, xs)
}

val root = Node("a", List(Node("w", Nil), Node("b", List(Node("c", List(Node("d", Nil))), Node("m", List(Node("n", Nil)))))))
val child = Node("t", Nil)
val ks = List("b", "m")

println("res: " + traverseAndAdd(root, root, child, ks))

I understand that here the list is immutable and even the code doesn't make any attempt to build the node ground up. I am asking for a suggestion on how can I achieve such a thing in Scala. Please help.

Also, I have already attempted the problem to which this problem is a sub problem using normal (not tail) recursion but I ended up with stackoverflow for the data is that huge. So thought of this approach!

Upvotes: 0

Views: 89

Answers (1)

jwvh
jwvh

Reputation: 51271

I noticed a few shortcomings in your code.

  • class Empty is defined but never used.
  • val k is populated but never used.
  • Your data structure does not require uniqueness so a given Node path is not guaranteed to be unique.

Here's what I was able to construct. It's not tail recursive, nor does it address the uniqueness issue, but it appears to work.

case class Node[A](elem: A, subNodes: List[Node[A]])

def addNode[T](node: Node[T], path: List[T]): Node[T] = {
  if (path.isEmpty)
    node
  else if (path.head == node.elem)
    addNode(node, path.tail)
  else if (node.subNodes.map(_.elem).contains(path.head))
    Node(node.elem, node.subNodes.map{n =>
      if (n.elem == path.head) addNode(n,path.tail)
      else n
    })
  else
    Node(node.elem
        ,node.subNodes :+ addNode(Node(path.head, List[Node[T]]()), path.tail))
}

val root = Node("a", List(Node("w", Nil)
                         ,Node("b", List(Node("c", List(Node("d", Nil)))
                                        ,Node("m", List(Node("n", Nil)))))))
addNode(root,List("a","b","m","n","t"))

Upvotes: 1

Related Questions