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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search 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.

&nbsp;
Example 1:
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
Input: root = []
Output: []

&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 104].
	0 &lt;= Node.val &lt;= 104
	The input tree is guaranteed to be a binary search tree.


class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        """
        if not root:
            return ""
        res = []
        def dfs(node):
            res.append(str(node.val))
            if node.left:
                dfs(node.left)
            if node.right:
                dfs(node.right)
        dfs(root)
        return ','.join(res)
    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        """
        if len(data) == 0:
            return []
        splitdata = data.split(",") 
        preorder = []
        for item in splitdata:
            preorder.append(int(item))          
        inorder = sorted(preorder)
        hash_map = {}  
        for i in range(len(inorder)):
            hash_map[inorder[i]] = i
        def helper(preorder, pstart, pend, inorder, istart, iend):
            if pstart > pend:
                return None
            elif pstart == pend:
                return TreeNode(preorder[pstart])

            root = TreeNode(preorder[pstart])
            
            rootindex = hash_map[preorder[pstart]]
            
            numleft = rootindex - istart
            
            root.left = helper(preorder, pstart+1, pstart + numleft, inorder, istart,rootindex-1 )
            root.right = helper(preorder, pstart + numleft +1, pend, inorder, rootindex +1, iend)
            
            return root
            
        return (helper(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1))
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder string = new StringBuilder();
        traverse(root, string);
        return string.toString();
    }

    private void traverse(TreeNode root, StringBuilder string){
        if(root == null) return;
        string.append(root.val).append(",");
        traverse(root.left, string);
        traverse(root.right, string);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty()) return null;

        String[] dataArr = data.split(",");

        TreeNode root = new TreeNode(Integer.parseInt(dataArr[0]));

        for(int i = 1; i < dataArr.length; i++)
            insert(Integer.parseInt(dataArr[i]), root);

        return root;
    }

    private void insert(int digit, TreeNode root){

        if(digit > root.val){
            if(root.right != null)
                insert(digit, root.right);
            else
                root.right = new TreeNode(digit);
        } else {
            if(root.left != null)
                insert(digit, root.left);
            else
                root.left = new TreeNode(digit);
        }

    }
}
class Codec
{
    public:

    string pre(TreeNode * root)
    {
        if(root==NULL)
            return "";

        int temp = root->val;
        string tempz = to_string(temp);

        string l = pre(root->left);
        string r = pre(root->right);

        return (tempz + "," + l + "," + r);
    }

    vector<int> parse_string(string data)
    {
        vector<int> ans;
        string temp = "";
        int n=data.size();

        for(int i=0;i<n; ++i)
        {
            if(data[i]==',')
            {
                if(temp.size()==0)
                    continue;
                else
                {
                    int val = stoi(temp);
                    ans.push_back(val);
                    temp="";
                }
            }
            else
                temp += data[i];
        }
        return ans;
    }

    TreeNode * make_tree(vector<int>& preorder, int min_val, int max_val, int& preorder_idx, int n)
    {
        if(preorder_idx == n)
            return NULL;
        int val = preorder[preorder_idx];
        if(min_val <= val and val <= max_val)
        {
            TreeNode * curr = new TreeNode(val);
            preorder_idx++;
            curr->left = make_tree(preorder, min_val, val-1, preorder_idx, n);
            curr->right = make_tree(preorder, val+1, max_val, preorder_idx, n);
            return curr;
        }
        else
            return NULL;
    }

    string serialize(TreeNode* root)
    {
        string traversal = pre(root);
        //cout<<traversal<<endl;
        return traversal;
    }

    TreeNode* deserialize(string data)
    {
        if(data.size()==0)
            return NULL;
        vector<int> traversal = parse_string(data);

        // for(auto x:traversal)
        // cout<<x<<" ";

        int preorder_idx = 0;
        TreeNode * root = make_tree(traversal, INT_MIN, INT_MAX, preorder_idx, traversal.size());

        return root;
    }
};
;/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    // Using Preorder traversal to create a string of BST
    // Preorder works in following way
    // root -> left -> right
    let preorder = [];
    
    function dfs(node) {
        if (node === null) return;
        // Get root value
        preorder.push(node.val);

        // Get All the Left values
        dfs(node.left);

        // Get all the right values
        dfs(node.right);
    }

    // call it with root
    dfs(root)

    // Turn into string and return it
    return preorder.join(',')
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if (data === "") return null;

    // Get numbers array from a string
    const preorder = data.split(',').map(Number);

    // using -Infinity and +Infinity as placeholder check
    function recur(lower = -Infinity, upper = Infinity) {
        // This condition useful for when we are filling left side of tree it'll avoid all the values greater then then its upper value by putting null init.
        if (preorder[0] < lower || preorder[0] > upper) return null;

        // If preorder become empty
        if (preorder.length === 0) return null;

        // Create a root node [shift method will change the original array]
        const root = new TreeNode(preorder.shift());

        // Here for left side of tree, we are using current root node's value as 'upper bound' (so higher values ignored).
        root.left = recur(lower, root.val);

        // Same as above for right side we are using root node's values as 'lower bound' (so lower values ignored);
        root.right = recur(root.val, upper);

        return root;
    }

    // Final root will be out BST
    return recur();
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
Serialize and Deserialize BST