binary trees (1)


Welcome to my first post: Serializing and Deserializing a binary tree

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.

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.

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.

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:

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.

Stay tuned.  We have more exciting posts coming….