CODEWITHSUNDEEP
algorithmscaladata-structurestree
mop
mop

Reputation: 433

how to build a tree then traverse every leaf (from root node to leaf every time)?

there is a file content as below("1.txt")

1.txt :

a,b
b,c
c,d
c,e
a,i
a,f
f,g
f,h

the tree structure like:

             a   
        b    i     f
    c            g   h
 d   e

expected:

a->b->c->d
a->b->c->e
a->i
a->f->g
a->f->h

Upvotes: 2

Views: 252

Answers (1)

rogue-one
rogue-one

Reputation: 11587

This should work. I have skipped the part where the tree is built from reading the text file since it is simple enough.

case class Node(node: String, children: Seq[Node] = Seq()) {
  override def equals(that: Any): Boolean =
      that match {
          case that: Node if this.node == that.node => true
          case _ => false
   }
  override def toString = node
}

val d= Node("d")
val e = Node("e")
val g = Node("g")
val h = Node("h")
val i = Node("i")
val c = Node("c", Seq(d,e))
val f = Node("f", Seq(g, h))
val b = Node("b", Seq(c))
val a = Node("a", Seq(b,f,i))

val tree = a :: b :: c :: d :: e :: f :: g :: h :: i :: Nil

def traverse(tree: Seq[Node]): Seq[Seq[Node]] = {
  import scala.annotation.tailrec
    val leafNodes = tree.filter(x => x.children.isEmpty)
    @tailrec    
    def walk(node: Node, descendants: Seq[Node] = Seq()): Seq[Node] = {
        tree.find(x => x.children.contains(node)) match {
          case Some(x) =>  walk(x, (descendants :+ node))
          case None => descendants :+ node
        }
    }
    leafNodes.map(walk(_, Seq()).reverse)
}

output:

scala> traverse(tree)
res26: Seq[Seq[Node]] = List(List(a, b, c, d), List(a, b, c, e), List(a, f, g), List(a, f, h), List(a, i))

Upvotes: 2

Related Questions