Problem Statement

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 tree. There is no restriction on how your serialization/deserialization algorithm should work. Ensure that a binary tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Examples

Example 1:

Input: root = [2, 1, 3]
Output: [2, 1, 3]

Example 2:

Input: root = [7, 3, 15, null, null, 9, 20]
Output: [7, 3, 15, null, null, 9, 20]

Different Approaches

1️⃣ Serialization

Intuition:

The concept of serializing a binary tree involves transforming its structure into a string format that preserves the hierarchical arrangement of nodes. By utilizing level-order traversal (BFS), we can ensure that nodes are processed in the order of their levels, which simplifies the reconstruction of the tree during deserialization. In this approach, each node's value is recorded in the string, while null nodes are represented by a special placeholder (e.g., "#") to maintain the integrity of the tree structure.

Approach:

1. First, check if the tree is empty. If the root is null, return an empty string. Otherwise, initialize an empty string to hold the serialized data of the binary tree.
2. Utilize a queue for level-order traversal. Begin by initializing a queue and enqueueing the root node.
3. In the level-order traversal process: Dequeue a node from the queue. If the node is null, append "#" to the string. If the node is not null, append its value followed by a comma (",") to the string and enqueue its left and right children.
4. Continue this process until the queue is empty, and then return the final string which contains the complete serialized representation of the binary tree.

2️⃣ Deserialization

Intuition:

Deserialization involves reconstructing a binary tree from its serialized string representation. The process relies on level-order traversal (BFS) to read the nodes in the sequence they appear in the serialized data, facilitating accurate tree reconstruction. Each node's value is extracted from the string, with null nodes represented by a specific character (e.g., "#") to denote the absence of a child node.

Approach:

1. Start by checking if the serialized string is empty. If it is, return null as there is no tree to reconstruct.
2. Split the serialized string into individual node values using a comma delimiter. The first value represents the root of the tree, which should be used to create the root node. Initialize a queue and enqueue the root node to facilitate level-order construction.
3. Perform level-order traversal: Dequeue a node from the queue. Read the next value from the tokenized data to determine the left child. If this value is "#", set the left child to null; otherwise, create a new node. Repeat the process for the right child. If the right child’s value is "#", set it to null; otherwise, create a new node. Enqueue both left and right children for further processing.
4. Continue the traversal until all nodes are processed and the queue is empty. Finally, return the root node of the fully reconstructed binary tree.

Code:

#include <bits/stdc++.h>
using namespace std;

// Definition for a binary tree node.
  struct TreeNode {
      int data;
      TreeNode *left;
      TreeNode *right;
       TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
  };
 

class Solution {
public:
    // Encodes the tree into a single string
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "";
        }

        // Initialize an empty string
        // to store the serialized data
        stringstream ss;
        // Use a queue for level-order traversal
        queue<TreeNode*> q;
        // Start with the root node
        q.push(root);

        // Perform level-order traversal
        while (!q.empty()) {
            // Get the front node in the queue
            TreeNode* curNode = q.front();
            q.pop();

            // Check if the current node is null and append "#" to the string
            if (curNode == nullptr) {
                ss << "#,";
            } else {
                // Append the value of the current node to the string
                ss << curNode->data << ",";
                // Push the left and right children to the queue for further traversal
                q.push(curNode->left);
                q.push(curNode->right);
            }
        }

        // Return the serialized string
        return ss.str();
    }

    // Decode the encoded data to a tree
    TreeNode* deserialize(string data) {
        if (data.empty()) {
            return nullptr;
        }

        // Use a stringstream to tokenize the serialized data
        stringstream s(data);
        string str;
        getline(s, str, ',');
        // Read the root value from the serialized data
        TreeNode* root = new TreeNode(stoi(str));

        // Use a queue for level-order traversal
        queue<TreeNode*> q;
        // Start with the root node
        q.push(root);

        // Perform level-order traversal to reconstruct the tree
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            // Read the value of the left child from the serialized data
            getline(s, str, ',');
            if (str != "#") {
                TreeNode* leftNode = new TreeNode(stoi(str));
                node->left = leftNode;
                q.push(leftNode);
            }

            // Read the value of the right child from the serialized data
            getline(s, str, ',');
            if (str != "#") {
                TreeNode* rightNode = new TreeNode(stoi(str));
                node->right = rightNode;
                q.push(rightNode);
            }
        }

        // Return the reconstructed root of the tree
        return root;
    }

    static void inorder(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
};

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    Solution solution;
    cout << "Original Tree: ";
    Solution::inorder(root);
    cout << endl;

    string serialized = solution.serialize(root);
    cout << "Serialized: " << serialized << endl;

    TreeNode* deserialized = solution.deserialize(serialized);
    cout << "Tree after deserialization: ";
    Solution::inorder(deserialized);
    cout << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) Both serialize and deserialize functions have a time complexity of O(N), where N is the number of nodes in the tree. This is because each function processes every node once.
• Space Complexity:O(N) Both serialize and deserialize functions have a space complexity of O(N). This space is used by the queue to hold nodes at various levels of the tree during traversal and reconstruction.