Serialize and Deserialize BST Explained | O(n) | Beats 98.41% 32ms | Queue | CPP
Here I have used pre-order traversal (root left right) to both serialize and deserialize the tree.\n\n## Serialize:\nThe main idea is when you are at any node o
### Here I have used pre-order traversal (root left right) to both serialize and deserialize the tree.\n\n## **Serialize:**\nThe main idea is when you are at any node of the tree, append its value to the string and push its children to the queue and continue till the queue is empty.\n\n**Things to note:** \n- Have a look at the constraints, directly appending to the string will only let you handle values within 7 bit range (char). So you have to devise some other way of appending to it correctly.\n- Here I have conveted the int to string using to_string() method and stored them space seperated.\n\n## **Deserialize:**\nThe idea for deserialization is similar to that of serialize, if the root is null, initialize the tree and push the children of root in the queue. Then pop nodes out from queue and keep putting data to the tree and its children to the queue until the string exhausts. \n\n**Things to note:**\n- You have to make sure you extract data from the string correctly in the format that you stored data in it.\n-  Here I used strtok() method to extract data from " " seperated string and atoi() method to convert the char* to int and put the value in the tree.\n\n\n```c++\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n */\nclass Codec {\npublic:\n\n    // Encodes a tree to a single string.\n    string serialize(TreeNode* root) {\n        if(root == NULL) return "";\n        string ans = "";\n        queue<TreeNode*> q;\n        q.push(root);\n        while(!q.empty()){\n            TreeNode *temp = q.front(); q.pop();\n            if(temp != NULL) {\n                ans+=to_string(temp->val) + " ";\n                q.push(temp->left);\n                q.push(temp->right);\n            }\n            else ans+="null ";\n        }\n        return ans;\n    }\n\n    // Decodes your encoded data to tree.\n    TreeNode* deserialize(string data) {\n        // reverse(data.begin(), data.end());\n        queue<TreeNode*> q;\n        TreeNode *ans=NULL;\n        char *dat = new char [data.size() + 1];\n        strcpy(dat, data.c_str());\n        char *token = strtok(dat, " ");\n        while(token!=NULL){\n            // cout << atoi(token) << endl; token = strtok(NULL, " ");\n            if(ans==NULL){\n                ans = new TreeNode(atoi(token));\n                token = strtok(NULL, " ");\n                q.push(ans);\n            }else{\n                TreeNode *temp = q.front(); q.pop();\n                if(strcmp(token, "null")) {temp->left = new TreeNode(atoi(token));\n                q.push(temp->left);}\n                token = strtok(NULL, " ");\n                if(token==NULL) break;\n                if(strcmp(token, "null")) {temp->right = new TreeNode(atoi(token));\n                q.push(temp->right);}\n                token = strtok(NULL, " ");\n            }\n        }\n        return ans;\n    }\n};\n\n// Your Codec object will be instantiated and called as such:\n// Codec* ser = new Codec();\n// Codec* deser = new Codec();\n// string tree = ser->serialize(root);\n// TreeNode* ans = deser->deserialize(tree);\n// return ans;\n```
[]