Serialize and Deserialize Binary Tree hard

Problem Statement

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 your OJ (Online Judge) is configured. You don't need to encode the null nodes explicitly.

Example 1

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

Example 2

Input: root = [] Output: []

Steps

The solution uses a preorder traversal for serialization and a recursive approach for deserialization.

Serialization (Preorder Traversal):

1. Start from the root node.
2. If the current node is not NULL, append its value followed by a comma to the string.
3. Recursively serialize the left subtree.
4. Recursively serialize the right subtree.
5. Handle NULL nodes by appending "N," to the string.

Deserialization (Recursive Approach):

1. Create a queue of strings from the serialized string using stringstream.
2. Recursively reconstruct the tree:
   • If the current string is "N", return NULL.
   • Create a new node with the value from the current string.
   • Recursively deserialize the left and right subtrees using the queue.

Explanation

The preorder traversal ensures a unique representation of the tree. The N placeholder in the serialized string indicates a null node, allowing the deserialization process to correctly reconstruct the tree's structure. The queue facilitates efficient access to the next node values in the serialized string during the recursive deserialization.

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

class Codec {
public:
    // Encodes a tree to a single string.
    std::string serialize(TreeNode* root) {
        std::stringstream ss;
        serializeHelper(root, ss);
        return ss.str();
    }

    void serializeHelper(TreeNode* node, std::stringstream& ss) {
        if (node == nullptr) {
            ss << "N,";
            return;
        }
        ss << node->val << ",";
        serializeHelper(node->left, ss);
        serializeHelper(node->right, ss);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(std::string data) {
        std::stringstream ss(data);
        std::string val;
        std::queue<std::string> q;
        while (std::getline(ss, val, ',')) {
            q.push(val);
        }
        return deserializeHelper(q);
    }

    TreeNode* deserializeHelper(std::queue<std::string>& q) {
        std::string val = q.front();
        q.pop();
        if (val == "N") return nullptr;
        TreeNode* node = new TreeNode(std::stoi(val));
        node->left = deserializeHelper(q);
        node->right = deserializeHelper(q);
        return node;
    }
};

Complexity

• Time Complexity: Both serialization and deserialization have a time complexity of O(N), where N is the number of nodes in the binary tree, because each node is visited once.

• Space Complexity: The space complexity is O(N) for both serialization and deserialization due to the recursive calls and the use of a queue (or implicit recursion stack). In the worst-case (a skewed tree), the recursion depth can be N.