Using lower bound and upper bound to deserialize BST
The idea is to encode every non null root value by preorder traversal \n\nwhen deserializing the tree, we can pass by the lower bound and upper bound to know th
The idea is to encode every non null root value by preorder traversal \n\nwhen deserializing the tree, we can pass by the lower bound and upper bound to know the boundary of a subtree.\n\nThis approach has an overhead of looking up one extra number, which would be O ( 2N )\n\n```\n    // Encodes a tree to a single string.\n    void serialize(TreeNode* root, ostringstream& out )\n    {\n        if ( !root ) return;\n        out << root->val << ",";\n        serialize(root->left, out);\n        serialize(root->right, out);\n    }\n    \n    string serialize(TreeNode* root) {\n        ostringstream ss;\n        serialize(root, ss);\n        return ss.str();\n    }\n\n    TreeNode* deserialize(const string& s, int lower, int upper, int & pos )\n    {\n        // pos is a variable to record the end of decoded buffer \n        if ( pos == s.size() ) return nullptr;\n        int cur_pos = pos;\n        int number = 0;\n        while( s[cur_pos] != ',')\n        {\n            number = number * 10 + s[cur_pos] - '0';\n            ++cur_pos;\n        }\n        ++cur_pos;\n        // The next number is not part of current subtree, should return nullptr\n        if ( number < lower || number > upper ) return nullptr;\n\n        TreeNode* root = new TreeNode( number );\n        pos = cur_pos; // update pos \n        root->left =  deserialize( s, lower, root->val, pos );\n        root->right = deserialize( s, root->val, upper, pos );\n        return root;\n    }\n    // Decodes your encoded data to tree.\n    TreeNode* deserialize(string data) {\n        int pos = 0;\n        return deserialize( data, INT_MIN, INT_MAX, pos );\n        \n    }\n```
[]