SimplePrefixTree.scala

case class SimplePrefixTree(prefix: String, leaves: Seq[SimplePrefixTree])

object SimplePrefixTree {

  def apply(stringSet: Set[String]): SimplePrefixTree = {
    val longestCommonPrefix = if (!stringSet.isEmpty) {
      (stringSet.min, stringSet.max).zipped.takeWhile(v => v._1 == v._2).unzip._1.mkString
    } else {
      ""
    }
    if (longestCommonPrefix.isEmpty) {
      val leaves = stringSet
        .filter(!_.isEmpty)
        .groupBy(_.charAt(0).toString)
        .values
        .map(SimplePrefixTree(_))
        .toSeq
      SimplePrefixTree("", leaves)
    } else {
      val remainingStrSet = stringSet.map(_.stripPrefix(longestCommonPrefix)).filter(!_.isEmpty)
      if (remainingStrSet.isEmpty) {
        SimplePrefixTree(longestCommonPrefix, Seq())
      } else {
        SimplePrefixTree(longestCommonPrefix, Seq(SimplePrefixTree(remainingStrSet)))
      }
    }
  }

}