Intuition

Deserialize the string in the exact same way we serialize the BST.

Solution

I chose to serialize the BST using preorder traversal. Thus, deserialize process needs to be completed with preorder traversal, too.

Algorithm

1. Use preorder and serialize BST, as serializing if we reach end of the tree, we put # character in the string to denote it has reached to the end. Also, we split the output of preorder traversal in root-left-right order. What I mean is we need to use some seperator character(in this case /) to know where any specific nodes left-subtree or right-subtree ends.
2. While deserializing, to make it easier, we change string to stringstream to process data easier. After converting serialized BST string to stringstream, we call helper function initially.
3. In the helper function, we declare a temporary string s and put the next token in it. This is the most important part. Since we're using stringstream, we can take the part until the next / character, this is exactly why we used a seperator character as serializing. Then, recursively we keep deserializing in the way we serialized the BST.

C++

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {	
        if(!root) return "#"; // ending character
        
		// seperator character - /
        return to_string(root->val) + '/' + serialize(root->left) + '/' + serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "#") return nullptr;
        
        stringstream stream(data);
        return helper(stream);
    }
    
    TreeNode* helper(stringstream& data) {
        string s;
        getline(data, s, '/');  // consume data until next seperator character '/'
        if(s == "#") return nullptr; // if we reach '#', then it means we reached the end
		
		// then keep repeating process recursively in the preorder way.
        TreeNode* root = new TreeNode(stoi(s));
        root->left = helper(data); 
        root->right = helper(data);
        return root;
    }

Time complexity: O(preorder) = O(n)
Space complexity: O(preorder) = O(n)