tree-serialize.scala

case class Node(value: Int,
                left: Option[Node] = None,
                right: Option[Node] = None)

object Serializer {
  private val pattern = """^(\d+)\((.*)\)$""".r
  private val treeOpen = '('
  private val treeClose = ')'
  private val separator = ','
  private val separatorLength = 1

  def serialize(nodeOption: Option[Node]): String = nodeOption match {
    case Some(Node(value, left, right)) =>
      val leftStr = serialize(left)
      val rightStr = serialize(right)
      s"$value$treeOpen$leftStr$separator$rightStr$treeClose"

    case None => ""
  }

  def deserialize(str: String): Option[Node] = str match {
    case pattern(value, inner) =>
      val (left, right) = splitInner(inner)
      Some(Node(value.toInt, deserialize(left), deserialize(right)))

    case _ => None
  }

  private def splitInner(inner: String): (String, String) = {
    var balance = 0
    val left = inner.takeWhile {
      case `treeOpen` => balance += 1; true
      case `treeClose` => balance -= 1; true
      case `separator` if balance == 0 => false
      case _ => true
    }

    val right = inner.drop(left.length + separatorLength)

    (left, right)
  }
}

val tree = Some(Node(
  1,
  Some(Node(2, Some(Node(3)))),
  Some(Node(4,
    Some(Node(5)),
    Some(Node(6))
  ))
))

val serialized = Serializer.serialize(tree)
var deserialized = Serializer.deserialize(serialized)

assert(tree == deserialized)