Serialize and deserialize a binary search tree(BST) to make the string to transmit or store as short as possible.

serialize-deserialize.cpp

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return string{};

        string code;
        serialize(root, code);
        return code;
    }

    void serialize(TreeNode* root, string& code) {
        if (!root) {
            code += '|'; // use '|' to indicate a leaf node
        }
        else {
            code += to_string(root->val) + ' '; // use a space to separate node values
            serialize(root->left, code);
            serialize(root->right, code);
        }
    }

    TreeNode* deserialize(string& code) {
        int val = decodeValue(code);

        if (val == -1) // leaf node or end-of-string
            return nullptr;
        else {
            // pre-order traversal
            TreeNode* node = new TreeNode(val);
            node->left = deserialize(code);
            node->right = deserialize(code);
        }
    }

    int decodeValue(string& code) {
        if (code.empty())
            return -1;
        else if (code[0] == '|') {
            code.erase(0, 1); // remove '|'
            return -1;
        }
        else {
            int val = stoi(code.substr(0, code.find_first_of(' ')));
            code.erase(0, code.find_first_of(' ')+1);
            return val;
        }
    }
};