DAY 61 - Serialize and Deserialize Binary Tree

Welcome to DAY 61. Today we will diverge once again into the Data Structure Trees and look at some more questions. I suggest reading the previous articles that I have written on Trees before reading this.

Question: Serialize and Deserialize Binary Tree

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.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

• Input: root = [1,2,3,null,null,4,5]
• Output: [1,2,3,null,null,4,5]

Intuition:

• The question is pretty easy. We need to convert a binary tree into a string first and then write a function to convert it back to a tree.
• Let's see how we can solve this. To make a binary tree into a string, we can just do level order traversal and push the value into a string by using to_string function to convert it.
• We also add comma characters as separators so we can clearly differentiate between the values.
• We also use a special character to identify null nodes and pass them as '%' here.
• The hard part is deserialzing. So here we use a queue and push the first character of the string as it's obviously the root.
• Next we use the same approach but this time instead of doing lvl order traversal. We check if the current node is '%'. So we know that the left of this node is a null.
• We do the same thing again to check for right. Remember level order traversal goes like bfs.
• Everytime we encounted that if it's not null we simply push it into queue and give it the appropriate parent.

Algorithm and Code:

Serialize Function:

• The serialize function traverses the binary tree in level-order using a queue (BFS).
• It starts by pushing the root node into the queue.
• While the queue is not empty, it dequeues a node, appends its value to the result string followed by a comma (,).
• If the node is not NULL, it enqueues its left and right children into the queue.
• If the node is NULL, it appends %, to the result string to represent a NULL node.
• The resulting string represents the serialized binary tree.

Deserialize Function:

• The deserialize function takes the serialized string as input and reconstructs the binary tree.
• It first checks if the input string is empty, in which case it returns NULL (empty tree).
• It uses a stringstream to tokenize the input string by commas (,).
• It retrieves the first value from the stringstream to create the root node of the binary tree.
• It initializes a queue and pushes the root node into the queue.
• While the queue is not empty, it dequeues a node and processes its left and right children.
• It retrieves the next value from the stringstream and creates a left child if the value is not %.
• It retrieves the next value from the stringstream and creates a right child if the value is not %.
• If the value is %, it represents a NULL child, so the corresponding child node is set to NULL.
• The process continues until all nodes are processed, and the original binary tree is reconstructed.

Code:

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

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

            }
        }

        return s;

    }

    // Decodes your encoded data to tree.
    // Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.size() == 0) return NULL;
    stringstream s(data);
    string str;
    getline(s, str, ','); // Get the first value from the stringstream

    TreeNode* root = new TreeNode(stoi(str));
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        // Process the left child
        getline(s, str, ','); // Get the next value from the stringstream
        if (str == "%") {
            node->left = NULL;
        } else {
            TreeNode* leftNode = new TreeNode(stoi(str));
            node->left = leftNode;
            q.push(leftNode);
        }
        // Process the right child
        getline(s, str, ','); // Get the next value from the stringstream
        if (str == "%") {
            node->right = NULL;
        } else {
            TreeNode* rightNode = new TreeNode(stoi(str));
            node->right = rightNode;
            q.push(rightNode);
        }
    }
    return root;
}

};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

Complexity Analysis:

Time: O(N)
Space: O(N)

Thanks for reading.