Well this is my first blog post ever and I want to be able to display code, so let’s see how this is going to work. I’ll probably do most of my posts in Swift.

Let’s say you had a binary search tree and you wanted to be able to serialize it and deserialize it. Ok so let’s define our binary tree as such.

1 2 3 4 5 6 7 8 9 |
class TreeNode { let val: Int var left: TreeNode? = nil var right: TreeNode? = nil init(_ val: Int) { self.val = val } } |

Let’s look at serialization first. To make the code a little simpler, I’m going to serialize the tree into an array which can always be joined together with a delimiter.

1 2 3 4 5 6 7 8 |
func serialize(node: TreeNode?) -> [Int] { guard let node = node else { return [] } var res:[Int] = [] res.append(node.val) res.append(contentsOf: serialize(node: node.left)) res.append(contentsOf: serialize(node: node.right)) return res } |

Now the astute amongst you will see that I chose my words carefully and I said that we want to serialize / deserialize a binary **search** tree. Unlike a binary tree, a binary **search** tree has the property that the value of the left child is less than the current node which is less than the value of the right child. We can exploit this property in our deserialization attempt.

1 2 3 4 5 6 7 8 9 |
func deserialize(arr: [Int]) -> TreeNode? { guard let rootElem = arr.first else { return nil } let leftsub = arr.dropFirst().filter { $0 <= rootElem } let rightsub = arr.dropFirst().filter { $0 > rootElem } let rootNode = TreeNode(rootElem) rootNode.left = deserialize(arr: leftsub) rootNode.right = deserialize(arr: rightsub) return rootNode } |

But what happens if we want to serialize a binary tree that is not a binary search tree. Here, we are not able to exploit the invariant property because there is none. In this case we need to manually add a delimiter. Let’s just choose -1 as our delimiter for now. When we run into a node that is nil we will return -1 in the serializer so the deserializer knows to move on then. Our serialization code becomes:

1 2 3 4 5 6 7 8 |
func serialize(node: TreeNode?) -> [Int] { guard let node = node else { return [-1] } var res:[Int] = [] res.append(node.val) res.append(contentsOf: serialize(node: node.left)) res.append(contentsOf: serialize(node: node.right)) return res } |

This is pretty much what we had before. On the deserialization side, we walk through the array and when we see a -1 we return nil to the calling entity, otherwise we deserialize the array as before.

1 2 3 4 5 6 7 8 9 10 11 |
func deserialize(arr: inout [Int]) -> TreeNode? { guard arr.count > 0 else { return nil } guard let rootElem = arr.first else { return nil } guard rootElem != -1 else { arr.remove(at: 0); return nil } let rootNode = TreeNode(rootElem) arr.remove(at: 0) rootNode.left = deserialize(arr: &arr) rootNode.right = deserialize(arr: &arr) return rootNode } |

Stay tuned. We have more exciting posts coming….