Custom (De)serialization with Scala (Scala DCP #003)
Tags: scala, challenge, beginners, dailycodingproblem
Published: 2020-03-09 20:31:10

[Daily Coding Problem](https://dailycodingproblem.com/) is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Scala, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

### Problem

> Given the root to a binary tree, implement `serialize(root)`, which serializes the tree into a string, and `deserialize(s)`, which deserializes the string back into the tree.
> 
> For example, given the following Node class
> 
> ```
> class Node:
>     def __init__(self, val, left=None, right=None):
>         self.val = val
>         self.left = left
>         self.right = right
> ```
> The following test should pass:
> ```
> node = Node('root', Node('left', Node('left.left')), Node('right'))
> assert deserialize(serialize(node)).left.left.val == 'left.left'
> ```

### Strategy

[See my discussion of this problem (and my Java implementation) here!](https://dev.to/awwsmm/java-daily-coding-problem-003-59ef)

### Code

I feel like I'm cheating a bit for these first few Daily Coding Problems, because I've solved them previously using Java. Maybe we can improve on the Java solution with Scala, though. Here's the `Node` class I defined in Java, without the `serialize` and `deserialize` methods:

```java
public class Node {

  private String val;
  private Node left;
  private Node right;

  public Node (String val, Node left, Node right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }

  public Node (String val, Node left) {
    this(val, left, null);
  }

  public Node (String val) {
    this(val, null, null);
  }

  public Node left() { return this.left; }

  public Node right() { return this.right; }

  public String val() { return this.val; }

}
```

Believe it or not, _all_ of this can be replaced with a _single_ line of Scala code:

```scala
case class Node (value: String, left: Node = null, right: Node = null)
```

A [`case class`](https://docs.scala-lang.org/tour/case-classes.html) in Scala is shorthand for a class which contains only immutable member variables. In the example above, `value`, `left`, and `right` will be assignable only when a `Node` object is created, and cannot be changed once that object is instantiated. `case class`es also define a [_companion object_](https://medium.com/@cachiama/demystifying-scala-case-classes-b4d756959dcd#:~:text=By%20default%2C%20scala%20creates%20a,known%20as%20the%20factory%20method.&text=Because%20of%20this%20factory%20method,to%20use%20the%20new%20keyword.) of the same name which can be used for (among other things) making object instantiation a bit less verbose.

The above Scala code also uses _default arguments_ to define `left` and `right` as `null` when they're not specified by the user. So a `Node` object can be created with zero, one, or two child `Node`s, without needing to define additional constructors.

Finally, `case class`es provide getters (but not setters, because of the aforementioned immutability) for all of the member variables defined in the argument list. They will have the same names as the arguments themselves.

So that single line of Scala code above allows us to do all of the following:

```scala
scala> val nA = Node("nA")
nA: Node = Node(nA,null,null)

scala> val nB = Node("nB", nA)
nB: Node = Node(nB,Node(nA,null,null),null)

scala> val nC = Node("nC", nB, nA)
nC: Node = Node(nC,Node(nB,Node(nA,null,null),null),Node(nA,null,null))

scala> nA.value
res4: String = nA

scala> nB.left
res5: Node = Node(nA,null,null)

scala> nC.right
res6: Node = Node(nA,null,null)
```

If all of the above benefits of `case class`es weren't enough, they also define a default `toString` method which prints the internal data in a nice, human-readable format, as seen above. In the Java example, we needed to write _that_ code, as well. To get the equivalent functionality of this _single line of Scala code_, we needed roughly __fifty lines of Java__. That's quite the reduction in complexity.

Next, I'd like to take a few artistic liberties. The problem asks us to define `serialize` and `deserialize` methods using (presumably) Python. Serializing an object really just means defining a `toString` method. In Python, the default `toString` equivalent is about as ugly as the default Java `toString`:

```python
Python 2.7.16 (default, Dec 13 2019, 18:00:32) 
[GCC 4.2.1 Compatible Apple LLVM 11.0.0 (clang-1100.0.32.4) (-macos10.15-objc-s on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> class Node:
...     def __init__(self, val, left=None, right=None):
...         self.val = val
...         self.left = left
...         self.right = right
... 
>>> node = Node('root', Node('left', Node('left.left')), Node('right'))
>>> print(node)
<__main__.Node instance at 0x10d312ab8>
```

When we `print` the `Node`, it is serialized into a string representation using an automatically defined method. [In Python, this method is called `__str__()`.](https://stackoverflow.com/a/57496151/2925434) Although `__str__()` can be redefined directly, the problem asks us to define a `serialize` method instead. Rather than reinventing the wheel, I would prefer to just use our default `toString` provided by our `Node` `case class` in Scala. The spirit of the problem is simply to be able to convert these objects to their string representations, then back into objects.

However, it's at this point that I'd like to draw your attention to something which may end up bring a problem during our deserialization process. Notice how our Scala `Node`s are serialized:

```scala
scala> Node("heyo")
res16: Node = Node(heyo,null,null)
```

The `Node` itself is denoted by the literal string `Node(`, followed by comma-separated arguments, then closed with a `)`. A straightforward deserialization might involve using these three things as sentinels:

1. the string `Node(` begins the definition of a `Node`
2. commas `,` separate the `value` from the `left` and `right` `Node`s, and
3. the character `)` ends the definition of the `Node`

You might be able to see how this could be abused. First, imagine someone simply doesn't want their `Node` to have a `value`, they might define:

```scala
scala> Node("null",null,null)
res19: Node = Node(null,null,null)

scala> Node(null,null,null)
res20: Node = Node(null,null,null)
```

Note how both of these `Node`s have the same string representation, even though they are really very different things. We can therefore `require` that the `value` of a `Node` is not equal to the string `"null"` by modifying the `case class` definition:

```scala
case class Node (value: String, left: Node = null, right: Node = null) {
  require(value != "null") }
```

Now the compiler will throw an `Exception` when our `value` is a string masquerading as a `null`:

```scala
scala> Node("null",null,null)
java.lang.IllegalArgumentException: requirement failed
  at scala.Predef$.require(Predef.scala:268)
  ... 29 elided
```

Alternatively, we could `override` the default `toString` method to have it surround the `value` with quotes. Something like...

```scala
scala> Node("null",null,null)
res42: Node = Node("null",null,null)

scala> Node(null,null,null)
res43: Node = Node(null,null,null)
```

This, I think, is a better solution. In addition to solving this `null` issue, it also allows users to put commas `,` within labels, which otherwise could result in confusing serialized outputs like:

```scala
scala> Node("null,null,null",null,null)
res42: Node = Node(null,null,null,null,null)
```

...this would be a bit more difficult to parse. If you don't think that's too bad, imagine a more pathological example:

```scala
scala> Node("null,Node(null,Node(null,null,null),null)",null,null)
res42: Node = Node(null,Node(null,Node(null,null,null),null),null,null)
```

So maybe it is best that we redefine the `toString` method, at least to surround the `value` in quotes. Below, we `override` the default `toString` method, and make use of [triple quotes](https://stackoverflow.com/a/25633265/2925434) to avoid having to escape the literal `"` characters within the string:

```scala
scala> case class Node (value: String, left: Node = null, right: Node = null) {
     |   override def toString = s"""Node("$value",$left,$right)""" }
defined class Node

scala> Node("null,Node(null,Node(null,null,null),null)",null,null)
res27: Node = Node("null,Node(null,Node(null,null,null),null)",null,null)
```

> Remember that we're defining `toString` and `fromString` rather than `serialize` and `deserialize`. This is to avoid having the methods `toString` and `serialize` do nearly (but not exactly) the same thing.

...now we can clearly tell where the `value` begins and ends, by looking for the `"` characters (or the syntax highlighting for strings). We can then sanitize user inputs by replacing any `"` characters which appear within the `value` with their escaped equivalents:

```scala
scala> case class Node (value: String, left: Node = null, right: Node = null) {
     |   override def toString = s"""Node("${value.replaceAll("\"", "\\\\\"")}",$left,$right)""" }
defined class Node

scala> Node("""Dwayne "The Rock" Johnson""",null,null)
res28: Node = Node("Dwayne \"The Rock\" Johnson",null,null)
```

Beautiful! Finally, we can parse the serialized output using [this clever recursive pattern matching technique](https://stackoverflow.com/a/39900313/2925434). The gist of this method is that we define a regular expression which matches `terminal` `Node`s (leaves) and another regular expression which matches `arbitrary` `Node`s. We try to match on the `terminal` regex and if that doesn't work, we try to match on the `arbitrary` one.

For our serialization technique, a `terminal` `Node` should match the pattern:

```scala
scala> val terminal = """Node\("((?:[^\"]|\")*)",null,null\)""".r
terminal: scala.util.matching.Regex = Node\("((?:[^\"]|\")*)",null,null\)

scala> val rock = Node("""Dwayne "The Rock" Johnson""",null,null)
rock: Node = Node("Dwayne \"The Rock\" Johnson",null,null)

scala> rock.toString match { case terminal(value) => println(s"$value") }
Dwayne \"The Rock\" Johnson

scala> val list = Node("My list is List(1,2,3)",null,null)
list: Node = Node("My list is List(1,2,3)",null,null)

scala> list.toString match { case terminal(value) => println(s"$value") }
My list is List(1,2,3)
```

> The `.r` at the end of the string indicates that it's a regular expression.

...but any arbitrary `Node` should match the pattern:

```scala
scala> val arbitrary = """Node\("((?:[^\"]|\\")*)",(null|Node\(.*\)),(null|Node\(.*\))\)""".r
arbitrary: scala.util.matching.Regex = Node\("((?:[^\"]|\\")*)",(null|Node\(.*\)),(null|Node\(.*\))\)

scala> val nodes = Node("null",rock,list)
nodes: Node = Node("null",Node("Dwayne \"The Rock\" Johnson",null,null),Node("My list is List(1,2,3)",null,null))

scala> nodes.toString match { case arbitrary(value, left, right) => println(s"$value -- $left -- $right") }
null -- Node("Dwayne \"The Rock\" Johnson",null,null) -- Node("My list is List(1,2,3)",null,null)

scala> rock.toString match { case arbitrary(value, left, right) => println(s"$value -- $left -- $right") }
Dwayne \"The Rock\" Johnson -- null -- null

scala> list.toString match { case arbitrary(value, left, right) => println(s"$value -- $left -- $right") }
My list is List(1,2,3) -- null -- null
```

The only remaining issue we have is when `value` is `null`, in which case `toString` throws a `NullPointerException`:

```scala
scala> val noll = Node(null,null,null)
java.lang.NullPointerException
  at Node.toString(<console>:14)
  at scala.runtime.ScalaRunTime$.inner$1(ScalaRunTime.scala:254)
  at scala.runtime.ScalaRunTime$.stringOf(ScalaRunTime.scala:259)
  at scala.runtime.ScalaRunTime$.replStringOf(ScalaRunTime.scala:267)
  at .$print$lzycompute(<console>:9)
  at .$print(<console>:6)
  at $print(<console>)
...
```

...we can avoid this by disallowing `null` `value`s in our constructor:


```scala
scala> case class Node (value: String, left: Node = null, right: Node = null) {
     |   require (value != null)
     |   override def toString = s"""Node("${value.replaceAll("\"", "\\\\\"")}",$left,$right)"""
     | }
defined class Node

scala> val noll = Node(null,null,null)
java.lang.IllegalArgumentException: requirement failed
  at scala.Predef$.require(Predef.scala:268)
  ... 29 elided
```

Note that empty `value` strings are still allowed, though

```scala
scala> val noll = Node("",null,null)
noll: Node = Node("",null,null)
```

Finally, using [this SO answer](https://stackoverflow.com/a/39900313/2925434) as a template, we can deserialize any arbitrary `Node`:

```scala
scala> def fromString(serialized: String): Node = {
     |   val arbitrary = """Node\("((?:[^\"]|\\")*)",(null|Node\(.*\)),(null|Node\(.*\))\)""".r
     |   serialized match {
     |     case arbitrary(value,left,right) => Node(
     |       value.replaceAll("\\\\\"", "\""),
     |       if (left == "null") null else fromString(left),
     |       if (right == "null") null else fromString(right))
     |   }
     | }
fromString: (serialized: String)Node

scala> println(rock.toString); println(fromString(rock.toString).toString)
Node("Dwayne \"The Rock\" Johnson",null,null)
Node("Dwayne \"The Rock\" Johnson",null,null)

scala> println(list.toString); println(fromString(list.toString).toString)
Node("My list is List(1,2,3)",null,null)
Node("My list is List(1,2,3)",null,null)

scala> println(nodes.toString); println(fromString(nodes.toString).toString)
Node("null",Node("Dwayne \"The Rock\" Johnson",null,null),Node("My list is List(1,2,3)",null,null))
Node("null",Node("Dwayne \"The Rock\" Johnson",null,null),Node("My list is List(1,2,3)",null,null))
```

And the final test...

```scala
scala> val node = Node("root",Node("left",Node("left.left")),Node("right"))
node: Node = Node("root",Node("left",Node("left.left",null,null),null),Node("right",null,null))

scala> fromString(node.toString).left.left.value == "left.left"
res34: Boolean = true
```

Nice!


### Discussion

This problem is, in essence, an exercise in string manipulation. We want to make sure that our nodes are serialized in such a way that there are no degenerate cases (where two distinct nodes are mapped to the same serialized form), and we want to make sure that the user can't throw a wrench in the deserialization process by defining a `value` with hard-to-parse characters like `"` and `,`. Since these are our delimiters, the user could very easily make deserialization much more difficult for us by including them.

Since this is essentially a string manipulation problem, and since I'm pretty experienced with regex, I decided to go in that direction. There may be a better or clearer way of solving this problem in Scala without regex, but my entire solution is only 10 lines of code:

```scala
case class Node (value: String, left: Node = null, right: Node = null) {
  require (value != null)
  override def toString = s"""Node("${value.replaceAll("\"", "\\\\\"")}",$left,$right)"""
}

def fromString(serialized: String): Node = {
  val arbitrary = """Node\("((?:[^\"]|\\")*)",(null|Node\(.*\)),(null|Node\(.*\))\)""".r
  serialized match {
    case arbitrary(value,left,right) => Node(
      value.replaceAll("\\\\\"", "\""),
      if (left == "null") null else fromString(left),
      if (right == "null") null else fromString(right))
  }
}
```

I think my solution is clear, simple, and probably about as performant as any string manipulation problem can be, but if you have a better (or different) solution, I'd love to see it!

---

All the code for my Daily Coding Problems solutions is available at [github.com/awwsmm/daily](https://github.com/awwsmm/daily).

Suggestions? Let me know in the comments.

If you enjoyed this post, please consider supporting my work by <a href='https://ko-fi.com/Z8Z811E9B'>buying me a coffee</a>!