Serialize and Deserialize Binary Tree

C++: Serialize and Deserialize Binary Tree

Thought Process

To serialize and deserialize a binary tree, we can use a level-order traversal (BFS). For serialization, we traverse the tree level by level and store each node's value in a string, using "null" to represent missing nodes. For deserialization, we reconstruct the tree by processing the serialized string and building the tree level by level. This approach ensures that the tree structure is preserved and reconstructed accurately.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        
        if(root == NULL)
            return "null";

        queue<TreeNode*> q;
        stringstream ss;
        q.push(root);

        while(!q.empty()){

            TreeNode *nod = q.front(); q.pop();
            if(nod == NULL){
                ss << "null,";
            }
            else{
                ss << nod->val << ",";
                q.push(nod->left);
                q.push(nod->right);
            }
        }
        string result = ss.str();
        result.pop_back();
        return result; // 1,2,3,null,null,4,5,null,null,null,null
    }

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

        // 1,2,3,null,null,4,5,null,null,null,null

        if(data=="null")
            return NULL;

        vector<string> nodes;
        string token;
        stringstream ss(data);
        while(getline(ss,token,',')){
            nodes.push_back(token);
        }

        TreeNode *root = new TreeNode(stoi(nodes[0]));
        queue<TreeNode*> q;
        q.push(root);

        int idx = 1;
        while(!q.empty() && idx<nodes.size()){

            TreeNode *nod = q.front(); q.pop();
            // Although no use but gives sense of seeing nodes[idx] & proceeding further
            string str = nodes[idx]; 

            if(nodes[idx]!="null"){
                nod->left = new TreeNode(stoi(nodes[idx]));
                q.push(nod->left);
            }
            idx++;
            
            if(nodes[idx]!="null"){
                nod->right = new TreeNode(stoi(nodes[idx]));
                q.push(nod->right);
            }
            idx++;
        }
        return root;
    }
};

Code Complexity

Time Complexity: O(n)

Both serialization and deserialization visit each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(n)

The space used by the queue during serialization and deserialization depends on the maximum number of nodes at any level. In the worst case, the space complexity is O(n).