Serialize and Deserialize BST - bst preorder queue

serialize_deserialize_bst.cpp

// Encodes a tree to a single string.
    void another(TreeNode* root,string &ans){
        if(root==NULL){
            return;
        }
        ans+=to_string(root->val)+",";
        another(root->left,ans);
        another(root->right,ans);
    }
    
    string serialize(TreeNode* root) {
        string ans = "";
        another(root,ans);
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* find(int curr,TreeNode* root){
        if(curr > root->val){
            if(root->right == NULL)
                return root;
            else
                return find(curr,root->right);
        }
        else if(curr <= root->val){
            if(root->left == NULL)
                return root;
            else
                return find(curr,root->left);
        }
        return NULL;
    }
    
    TreeNode* deserialize(string s) {
        queue<int> data;
        string st="";
        for(int i=0;i<s.length();i++){
            if(s[i]!=','){
                st+=s[i];
            }
            if(s[i]==','){
                data.push(stoi(st));
                st="";
            }
        }
        if(data.empty()){
            return NULL;
        }
        TreeNode* root = new TreeNode(data.front());
        data.pop();
        int curr;
        while(!data.empty()){
            curr = data.front();
            data.pop();
            TreeNode* node = find(curr,root);
            TreeNode* temp = new TreeNode(curr);
            if(curr > node->val){
                node->right = temp;
            }
            if(curr < node->val){
                node->left = temp;
            }
        }
        return root;
    }

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just 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.

The idea is to first convert the given bst into a string maintaining the order of nodes. Traversing bst in preorder preserves the insertion order of the bst. Hence store the node separated by a comma in a string by their preorder traversal.

To deserialize we will use this preorder traversal and one by one keep inserting the nodes in a new tree. Each node will be inserted based on the bst property. Function 'find' finds the exact place where the new node will be inserted in the tree based on the bst property. We will first convert the nodes from string to a queue. We run till queue becomes empty and for each value, we run the find duction to find the root of the current node and make it its children.