Leetcode Serialize and Deserialize BST problem solution

YASH PAL,

In this Leetcode Serialize and Deserialize BST problem solution 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.

Leetcode Serialize and Deserialize BST problem solution

Problem solution in Python.

class Codec:

    def serialize(self, root):
        if not root:
            return "X,"
        
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        return str(root.val) + "," + left + right
            
        
    def deserialize(self, data):
        
        def helper(q):
            val = q.pop(0)
            if val == 'X':
                return None
            
            node = TreeNode(int(val))
            node.left = helper(q)
            node.right = helper(q)
            
            return node
               
        #print(data)
        t = data.split(',')
        t.pop()
        #print(t)
        
        return helper(t)

Problem solution in Java.

public String serialize(TreeNode root) {
        
        if(root == null)
            return null;
        
        String result = null;
        StringBuilder tree = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while(!q.isEmpty()) {
            
            TreeNode node = q.poll();
            if(node != null) {
                tree.append(node.val);
                tree.append(" ");
            
                q.add(node.left);
                q.add(node.right); 
               
            } else  {
                tree.append("null");
                tree.append(" ");
            }
            
        }
        return tree.toString().trim();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null)
            return null;
            
        String[] nodes = data.split(" ");    
        int i = 0;
        TreeNode root = toNode(nodes, i++);
        
        Queue<TreeNode> q = new LinkedList<>(); 
        q.add(root);
        
        while(i < nodes.length) {
            int size = q.size();
            while(size-- > 0 && i<nodes.length ) {
            
            TreeNode node = q.poll();
            node.left = toNode(nodes, i++);
            node.right = toNode(nodes, i++);
            
             if(node.left != null) {
               q.add(node.left);
             }
           
             if(node.right != null) {
               q.add(node.right);
             } 

         } // End of inner while loop
        }   
        return root;
    }
    
    //Create Node
    private TreeNode toNode(String[] nodes, int index) {
        
        if(index >= nodes.length || "null".equals(nodes[index]))
            return null;
        
        return new TreeNode(Integer.parseInt(nodes[index]));
    }

Problem solution in C++.

class Codec {
public:
    string ser;
    string dser;
    int i;
    void serialhelp(TreeNode *root){
        if(!root){
            ser+="N,";
            return;
        }
        ser+=to_string(root->val)+",";
        serialhelp(root->left);
        serialhelp(root->right);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ser="";
        serialhelp(root);
        return ser;
    }

    TreeNode *helper(queue<string>&q){
        string ch = q.front();
        q.pop();
        if(ch=="N") return NULL;
       TreeNode *root= new TreeNode(stoi(ch));
             root->left= helper(q);
        root->right=helper(q);
            return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string>q;
        string s="";
        for(int i=0;i<data.size();i++){
            if(data[i]==','){
                q.push(s);
                s="";
                continue;
            }
            s+=data[i];
        }
        return helper(q);
    }
};

Problem solution in C.

#ifdef WIDE_RANGE
#define KEY_MASK    0x1ffff
typedef uint32_t keyy_t;
#else
#define KEY_MASK    0xffff
typedef uint16_t keyy_t;
#endif // WIDE_RANGE

#define KEY(a)      ((uintptr_t)(a) & KEY_MASK)

struct srlz_data {
    int val;
    keyy_t loff, roff;   
} __attribute__ ((packed));

struct srlz {
    size_t sz;
    size_t n;
    struct srlz_data z[100000];
} __attribute__ ((packed));
    
char* serialize(struct TreeNode* root) {
    int of[KEY_MASK] = { 0 }, i = 1, k;
    struct TreeNode *n[10000] = { root };
    struct srlz *d = malloc(sizeof *d);
    struct srlz_data *z = d->z;
    d->sz = sizeof *d;
    of[KEY(root)] = i++;        
    for (int f = 0, b = 1 ; root && f < b ; f++) {
        z[of[k = KEY(n[f])]].val = n[f]->val;
        z[of[k]].loff = n[f]->left ? of[KEY(n[b++] = n[f]->left)] = i++ : 0;
        z[of[k]].roff = n[f]->right ? of[KEY(n[b++] = n[f]->right)] = i++ : 0;
    }
    return d->n = root ? i : 0, (char *)d;
}

struct TreeNode* deserialize(char* data) {
    struct srlz *d = (void *)data;
    struct srlz_data *z = d->z + 1;
    size_t c = d->n;
    struct TreeNode *n[100000] = { [1] = c ? malloc(sizeof **n) : NULL };
    for (int i = 1 ; i < c ; n[i++]->val = z++->val) {
        n[i]->left = z->loff ? n[z->loff] = malloc(sizeof **n) : NULL;
        n[i]->right = z->roff ? n[z->roff] = malloc(sizeof **n) : NULL;
    }
    return n[1];
}

coding problems