28. Serialize and Deserialize BST

Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

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

Example 2:

Input: root = []
Output: []

Solution:

Perform an preorder traversal and store the num with , separated Perform split and store numbers in a queue Build tree using a queue

  // 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:
    void createString(TreeNode *root, string &res)
    {
        if (root == NULL)
        {
            return;
        }
        
        res += to_string(root->val) + ',';
       
        createString(root->left, res);
        createString(root->right, res);
        return;
    }

    TreeNode *createTree(queue<int> &q, int min, int max)
    {
        
        if(q.empty()){
            return NULL;
        }

        int val = q.front();

        if (val < min || val > max)
        {
            return NULL;
        }
        
        q.pop();

        TreeNode *t = new TreeNode(val);

        t->left = createTree(q, min, val);
        t->right = createTree(q, val, max);

        return t;
    }

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

        string s = "";
        if (root == NULL)
        {
            return s;
        }
       
        createString(root, s);
        s.pop_back();
        return s;
    }

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

        if (data == "")
        {
            return NULL;
        }

        queue<int> q;

        int start = 0;
        int token = data.find(',');
        int num = 0;
        while (token != -1)
        {
            string k = data.substr(start, token - start);
            num = stoi(k);
            q.push(num);
            start = token + 1;
            token = data.find(',', start);
        }
        string k = data.substr(start, token - start);
        num = stoi(k);
        q.push(num);

        TreeNode *t = createTree(q, INT_MIN, INT_MAX);
        return t;
    }
};

Time Complexity: O(n)