Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as “[1,2,3,null,null,4,5]”
Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Binary Tree Serialization Algorithm using Depth First Search (Inorder Traversal)

The easiest way to serialize a binary tree is to use the depth first search (which is usually implemented using Recursion) to perform a in-order traversal. For example the following binary tree will be serialized into “1(2)(3)”

    1
   / \
  2   3

In the form of “ROOT(LEFT)(RIGHT)” or “ROOT(LEFT)” where the right definition can be omitted if it is null. The LEFT and RIGHT tree definitions are recursive as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "";
        }
        string s = std::to_string(root->val) + 
            "(" + serialize(root->left) + ")";
        if (root->right != nullptr) {
            s += "(" + serialize(root->right) + ")";
        }
        return s;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "";
        }
        string s = std::to_string(root->val) + 
            "(" + serialize(root->left) + ")";
        if (root->right != nullptr) {
            s += "(" + serialize(root->right) + ")";
        }
        return s;
    }
}

The recursive binary tree seralization algorithm is much straightforward.

Binary Tree DeSerialization Algorithm

The de-serialization process is a bit tricky, which we already discussed in this post: How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string s = data;
        if (s.size() == 0) {
            return nullptr;
        }
        if (s[0] == ')') return nullptr;
        int j = 0;
        while (j < s.size() && s[j] != '(') j ++;
        TreeNode* root = new TreeNode(std::stoi(s.substr(0, j)));
        int left = 0, i = j;
        // find separation between left and right definition
        while (i < s.size()) {
            if (s[i] == '(') {
                left ++;
            } else if (s[i] == ')') {
                left --;
            }
            if (left == 0) {
                break;
            }
            i ++;
        }
        if (j < s.size() - 1) {
            root->left = deserialize(s.substr(j + 1, i - 1 - j));
        }
        if (i + 1 < s.size() - 1) {
            root->right = deserialize(s.substr(i + 2, s.size() - i - 2));   
        }
        return root;        
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string s = data;
        if (s.size() == 0) {
            return nullptr;
        }
        if (s[0] == ')') return nullptr;
        int j = 0;
        while (j < s.size() && s[j] != '(') j ++;
        TreeNode* root = new TreeNode(std::stoi(s.substr(0, j)));
        int left = 0, i = j;
        // find separation between left and right definition
        while (i < s.size()) {
            if (s[i] == '(') {
                left ++;
            } else if (s[i] == ')') {
                left --;
            }
            if (left == 0) {
                break;
            }
            i ++;
        }
        if (j < s.size() - 1) {
            root->left = deserialize(s.substr(j + 1, i - 1 - j));
        }
        if (i + 1 < s.size() - 1) {
            root->right = deserialize(s.substr(i + 2, s.size() - i - 2));   
        }
        return root;        
    }
};

–EOF (The Ultimate Computing & Technology Blog) —