Serialize and Deserialize Binary Tree - queue level order

serialize_deserialize_tree.cpp

// Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        string s;
        while(!q.empty()){
            TreeNode* temp = q.front();
            q.pop();
            if(temp==NULL){
                s+="N,";
            }else{
                s+=(to_string(temp->val))+",";
                q.push(temp->left);
                q.push(temp->right);
            }
        }
        return s;
    }

    
    TreeNode* deserialize(string A) {
        cout<<A;
        if(A[0]=='N'){
            return NULL;
        }
        vector<string> vec;
        string temp="";
        for(int i=0;i<A.length();i++){
            if(A[i]!=','){
                temp+=A[i];
            }else{
                vec.push_back(temp);
                temp="";
            }
        }
        int j=0;
        TreeNode* root = new TreeNode(stoi(vec[0]));
        queue<TreeNode*> q;
        q.push(root);
        while(j < vec.size() && !q.empty()){
            TreeNode* temp = q.front();
            q.pop();
            if(temp!=NULL){
                if(vec[j+1]=="N"){
                    temp->left=NULL;
                    q.push(NULL);
                }else{
                    TreeNode* node = new TreeNode(stoi(vec[j+1]));
                    temp->left = node;
                    q.push(node);
                }
                if(vec[j+2]=="N"){
                    temp->right=NULL;
                    q.push(NULL);
                }else{
                    TreeNode* node = new TreeNode(stoi(vec[j+2]));
                    temp->right = node;
                    q.push(node);
                }
                j=j+2;
            }
        }
        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 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.

As an example, this would be the encoding,

    1
   / \
  2   3
     / \
    4   5
[1,2,3,N,N,4,5,N,N,N,N,]

To keep the structure of the tree intact in serialize, we perform the level order and store the node including NULL in a space-separated string. To perform level order I used a queue.

To deserialize I first convert the string to a vector of strings. I used a vector of strings to store the null nodes. I maintain an index 'j' that stores the location of the child of the current node. We start with the root and j+1 and j+2 points to its two children. Then based on their content we join the current node with its children and push them in the queue. Then increment j by two places. Repeat till the queue is not empty.