Serialize and Deserialize a Binary Tree

About the problem:

In this problem we are to convert a data structure or object into a sequence of bits, by means of which it can be stored in a file or memory buffer, or transmitted across a network (this is called serialization), which then can be reconstructed into the same using deserialization.

We can use various algorithms to do the serialization and deserialization to convert a binary tree into a string and then obtain the binary tree from the string.

TreeNode structure:

1
2
3
4
5
struct Treenode {
  int val;
  Treenode * left;
  Treenode * right;
};

Example 1:

Input: [ 4, 18, 11, null, 29, null, 15, 35, 6 ]

Output: [ 4, 18, 11, null, 29, null, 15, 35, 6 ]

Explanation: After serializing the tree-

Using the preorder traversal solution:

Preorder serialized string: “4,18,#,29,35,#,#,6,#,#,11,#,15,#,#”

Using  the postorder traversal solution:

Postorder serialized string: “#,#,#,35,#,#,6,29,18,#,#,#,15,11,4”

Deserializing the tree using one of the two above strings we should get the same tree. i.e, [ 4, 18, 11, null, 29, null, 15, 35, 6 ]

Example 2:

Input : [ 6, 16, null, 9, 10, 9, 6 ]

Output: [ 6, 16, null, 9, 10, 9, 6 ]

Explanation: After serializing the tree-

Using the preorder traversal solution:

Preorder serialized string: “6,16,9,9,#,#,6,#,#,10,#,#,#”

Using the postorder traversal solution:

Postorder serialized string: “#,#,9,#,#,6,9,#,#,10,16,#,6”

Deserializing the tree using one of the two above strings we should get the same tree. i.e, [ 4, 18, 11, null, 29, null, 15, 35, 6 ]

We will be using different binary tree traversal methods to solve this problem. While serializing, in the case of encountering a null value we will use a special character like “#” instead and for the value, we convert them into a string.

Approach #1: Post-order Traversal

Serialization- In this approach, we will first serialize the left subtree, then the right subtree, and then the root, all recursively.

Algorithm:

1. If root is null return the special character “#”.

2. Declare two variables, left and right to store the serialized string from the left and right subtree respectively.

3. Now return the concatenation of left, right, and root values separated by “,” into one string.

Code:

1
2
3
4
5
6
7
string serialize(TreeNode * root) {
  if (!root)
    return "#";
  string left = serialize(root - > left);
  string right = serialize(root - > right);
  return left + ',' + right + ',' + to_string(root - > val);
}

Deserialization- Now to deserialize we again use postorder. Here, we just first retrieve the number from the string then recursively call for right and left respectively.

Algorithm:

1. If the string is empty, return NULL.

2. To calculate the number or value from the string we traverse from the end until we find “,”.

3. Now we equate the current node value to the obtained one and recursively make two calls, one for right and left respectively.

4. Return the current node at last.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
TreeNode * deserialize(string & data) {
  if (data.back() == '#') {
    data.pop_back();
    if (data.size())
      data.pop_back();
    return NULL;
  }
  int n = 0;
  for (int i = data.size() - 1, j = 1; i >= 0 && data[i] != ','; i--, j *= 10) {
    if (data[i] == '-')
      n = -n;
    else
      n += (data[i] - '0') * j;
    data.pop_back();
  }
  if (data.size())
    data.pop_back();
  TreeNode * root = new TreeNode(n);
  root - > right = deserialize(data);
  root - > left = deserialize(data);
  return root;
}

Approach #2: Pre-order Traversal

Serialization- In this approach, we will first serialize the root, then the left subtree, and then the right subtree, all recursively.

Algorithm:

1. If root is null return the special character “#”.

2. Declare two variables, left and right to store the serialized string from the left and right subtree respectively.

3. Now return the concatenation of root value, left and the right separated by “,” into one string.

Code:

1
2
3
4
5
6
7
    string serialize(TreeNode * root) {
      if (!root)
        return "#";
      string left = serialize(root - > left);
      string right = serialize(root - > right);
      return to_string(root - > val) + ',' + left + ',' + right;
    }

Deserialization- Now to deserialize we again use preorder. Here, we just first retrieve the number from the string then recursively call for left and right respectively.

Algorithm:

1. If the string is empty, return NULL.

2. To calculate the number or value from the string we traverse from the start until we find “,”.

3. Now we equate the current node value to the obtained one and recursively make two calls, one for right and left respectively.

4. Return the current node at last.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
TreeNode * deserialize(string data) {
  int pos = 0;
  return preorder(data, pos);
}

TreeNode * preorder(string data, int & pos) {
  if (pos >= data.size()) return NULL;

  int pos1 = data.find_first_of(",", pos);
  if (pos1 == string::npos) {
    pos1 = data.size();
  }

  TreeNode * root;
  string vals = data.substr(pos, pos1 - pos);
  pos = pos1 + 1;
  if (vals == "#") {
    root = NULL;
    return root;
  }

  int val = atoi(vals.c_str());
  root = new TreeNode(val);

  root - > left = preorder(data, pos);
  root - > right = preorder(data, pos);
  return root;
}

Note: Like preorder and postorder we cannot use inorder as it is difficult to locate the root node in the serialized string as root is visited in between the left and right subtree.

Time complexity

All the above algorithms take O(n) time complexity, as they traverse through each node once.

Advantages of serialization and deserialization

• Serialization allows us to transfer an item across a network by converting it to a byte stream. It also helps to maintain the object’s condition.

• Deserialization takes less time to construct an object than creating an object from a class. This holds in general and is not specific to our implementation.

• By serializing the object into byte streams and then deserializing it, it is simple to clone.

• Serialization aids in the implementation of software persistence. It facilitates the direct storage of objects in databases as byte streams. This is advantageous because the information is immediately accessible any time it is required.

• It’s simple to use and can be tailored to your preferences.

• The serialized stream can be encrypted, authenticated, and compressed to meet the security requirements of Java.

• Serialized classes can provide consistent versioning and are adaptable enough to allow your application’s object model to evolve over time.

• Using third-party vendor libraries within C++, serialization may also be used to exchange objects between Java and C++ libraries.

• RMI, JavaBeans, and EJB are just a few of the essential technologies that rely on serialization. Java uses a different algorithm for serialization and deserialization from what we presented in this article.