1
\$\begingroup\$

Given a tree structure (in this example it a list of some nested group nodes), what is the best way to get all branches (branch = list of nodes from root to the leaf element)?

My solution (here root element = element with parent link to itself):

case class Group(id: Int, parent: Int)

def getBranches(groups: Seq[Group]) = {
  @tailrec
  def getPaths(paths: Seq[Seq[Group]], nodes: Seq[Group]): Seq[Seq[Group]] = nodes match {
    case group :: tail =>
      paths.find(_.head.id == group.parent) match {
        case Some(parentPath) => getPaths(paths :+ (group +: parentPath), tail)
        case None => getPaths(paths, tail :+ group)
      }
    case Nil => paths
  }

  def getBranchesOnly(paths: Seq[Seq[Group]]) = {
    for(path <- paths if !paths.exists { otherPath => 
      otherPath != path && otherPath.contains(path.head)
    }) yield path
  }

  val (roots, nodes) = groups.partition(gr => gr.parent == gr.id)
  val paths = getPaths(roots.map(Seq(_)), nodes)
  getBranchesOnly(paths)
}

A node has arbitrary number of children. All id are globally unique. Order of children in a node is irrelevant.

So given a tree:

    1
  2   3
4  5

its list of nodes is:

val groups = Seq(Group(4, 2), Group(1, 1), Group(2, 1), Group(5, 2), Group(3, 1))

I wonder if there is some existing algorithm or just a better approach for this task.

\$\endgroup\$
  • \$\begingroup\$ Does it have to use that tree representation (Seq[Group[)? Would a better tree implementation be acceptable? Or a solution which took the Seq as input and transformed it into such a structure? \$\endgroup\$ – itsbruce Sep 11 '15 at 1:44
  • \$\begingroup\$ Also, can you be more specific about the nature of the tree (binary, balanced, sorted etc.)? \$\endgroup\$ – itsbruce Sep 11 '15 at 1:48
  • \$\begingroup\$ @itsbruce I get tree nodes (id, parentId) from persistent storage, so a solution has to take it as input, but any inner representation is acceptable. The tree itself doesnt' have any specific properties/nature. Consider it as representation of arbitrary group/categories structure. \$\endgroup\$ – Tyth Sep 11 '15 at 5:35
  • \$\begingroup\$ Ah, ok. And the characteristics of the tree? Looks at least to be binary and sorted. \$\endgroup\$ – itsbruce Sep 11 '15 at 5:39
  • 1
    \$\begingroup\$ Thank you :) I will write up an answer later today. If anybody else beats me to it, they'll have benefited from our discussion. It might be an idea for you to add this information to the question, though. \$\endgroup\$ – itsbruce Sep 11 '15 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.