Каковы разные способы найти корень на карте, которая представляет дерево в Scala

Question

Как мне найти корень на карте, который представляет собой связующее дерево в Scala.

Ниже приведен пример карты, которая содержит дерево.

val l = List((1,List(2,3,4)), (2,List(5,6)), (3,List(7,8,9)))
val m1 = l.groupBy(_._1).map{ case (k, v) => (k, v.map(_._2))}

Answer 1

Это однострочник, который возвращает список всех узлов, которые не отображаются ни в одном из списков листьев.

l.collect{ case (k, _) if !l.exists(_._2.contains(k)) => k }

Более эффективная двухстрочная версия:

val leaves = l.flatMap(_._2).toSet
l.collect{ case (k, _) if !leaves.contains(k) => k }

Еще более эффективно:

val leaves: Set[Int] = l.flatMap(_._2)(collection.breakOut)
l.collect{ case (k, _) if !leaves.contains(k) => k }

Все они возвращают List(1) для данных выборки.