3.5) Serialize/Deserialize Binary Tree

    1
   / \
  2   3
     / \
    4   5

#include <iostream>
#include <sstream>
#include <queue>

using namespace std;

// 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) {
        if (!root)
            return "null"; // Represent null node as "null"

        // Serialize left and right subtrees recursively
        string left = serialize(root->left);
        string right = serialize(root->right);

        // Combine the serialization of root, left, and right subtrees
        return to_string(root->val) + "," + left + "," + right;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> nodes;
        stringstream ss(data);
        string token;

        // Split the serialized string by comma and store in a queue
        while (getline(ss, token, ','))
            nodes.push(token);

        return deserializeHelper(nodes);
    }

private:
    TreeNode* deserializeHelper(queue<string>& nodes) {
        string val = nodes.front();
        nodes.pop();

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

        TreeNode* root = new TreeNode(stoi(val));

        // Recursively deserialize left and right subtrees
        root->left = deserializeHelper(nodes);
        root->right = deserializeHelper(nodes);

        return root;
    }
};
// Function to print the in-order traversal of a binary tree
void printInOrder(TreeNode* root) {
    if (root) {
        printInOrder(root->left);
        cout << root->val << " ";
        printInOrder(root->right);
    }
}


int main() {
    // Create the binary tree
    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);

    // Initialize the codec
    Codec codec;

    // Serialize the binary tree
    string serialized = codec.serialize(root);
    cout << "Serialized Tree: " << serialized << endl;

    // Deserialize the string back into a binary tree
    TreeNode* deserializedRoot = codec.deserialize(serialized);

    // Print the deserialized tree (in-order traversal)
    cout << "Deserialized Tree (In-order): ";
    printInOrder(deserializedRoot);
    cout << endl;

    return 0;
}