29. Serialize and Deserialize Binary Tree

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.

Clarification: The input/output 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.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

Solution:

Similar to BST but in serialization we use "#" for NULL Nodes

 // 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:
    TreeNode *createTree(queue<string> &q)
    {
        if (q.empty())
        {
            return NULL;
        }

        string k = q.front();
        q.pop();

        if (k == "#")
        {
            return NULL;
        }

        int num = stoi(k);
        TreeNode *t = new TreeNode(num);

        t->left = createTree(q);
        t->right = createTree(q);

        return t;
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {

        if (root == NULL)
        {
            return "#";
        }

        string lt = serialize(root->left);
        string rt = serialize(root->right);

        return to_string(root->val) + ',' + lt + ',' + rt;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {

        queue<string> q;
        int start = 0;
        int token = ',';

        int end = data.find(token);

        while (end != -1)
        {
            string k = data.substr(start, end - start);
            q.push(k);
            start = end + 1;
            end = data.find(token, start);
        }
        string k = data.substr(start, end - start);
        q.push(k);

        TreeNode *t = createTree(q);
        return t;
    }
};

Time Complexity: O(n)