Python solution
One can use the encoding and decoding scheme in 297. Serialize and Deserialize Binary Tree. However, it does not use the properties of a BST: The left (right) s
One can use the encoding and decoding scheme in 297. Serialize and Deserialize Binary Tree. However, it does not use the properties of a BST: The left (right) subtree of a node contains only nodes with keys smaller (greater) than the node\'s key. Therefore, the encoding strings there does not satisfy the requirement that it should be as compact as possible. In particular, the null nodes need to be specified in the encoding string, and is redundant here. With the aforementioned BST property, one can actually recover a BST from its preorder traversal alone (without specifying the null nodes), assuming that the node values are distinct.\n\nAs a concrete example, suppose the preorder traversal of some BST gives `s = "5,4,2,3,7,9,10"`. Since the preorder traversal traverses the tree in the order `root -> left subtree -> right subtree`, we know that `"5"` must be the value of the `root` of the BST. Furthermore, by the BST property, all values smaller (larger) than `5` should be all values of nodes from the left (right) subtree. Hence, we we just need to iterate over `s[1:]` and find the first occurence (at index `i`) of some number larger than `5`. Then the left subtree would consists of values `s[1:i]` (`["4","2","3"]` in this example), and the right subtree would consists of values `s[i:]` (`["7","9","10"]` in this example). Calling the deserialize method recursively on `s[1:i]`, and `s[i:]` gives us the roots of the left subtree `l` and right subtree `r` respectively. And by assigning `root.left = l`, and `root.right = r`, and returning `root`, we finish the deserialization procedure.\n\nTime complexity for `serialize`: `O(n)`. Time complexity for `deserialize`: `O(n^2)`. Space complexity for both `serialize` and `deserialize`: `O(n)`.\n\n\n```\nclass Codec:\n\n    def serialize(self, root):\n        """Encodes a tree to a single string.\n        \n        :type root: TreeNode\n        :rtype: str\n        """\n        def dfs(root):\n            if not root:\n                return \n            res.append(str(root.val) + ",")\n            dfs(root.left)\n            dfs(root.right)\n            \n        res = []\n        dfs(root)\n        return "".join(res)\n\n    def deserialize(self, data):\n        """Decodes your encoded data to tree.\n        \n        :type data: str\n        :rtype: TreeNode\n        """\n        def helper(arr, i, j):\n            if i > j:\n                return\n            if i == j:\n                node = TreeNode(arr[i])\n                return node\n            for k in range(i+1, j+1):\n                if arr[k] > arr[i]:\n                    l = helper(arr, i+1, k-1)\n                    r = helper(arr, k, j)\n                    root = TreeNode(arr[i])\n                    root.left = l\n                    root.right = r\n                    return root\n            l = helper(arr, i+1, j)\n            root = TreeNode(arr[i])\n            root.left = l\n            return root\n        \n        arr = data.split(",")\n        arr.pop()\n        data = [int(x) for x in arr]\n        return helper(data, 0, len(data)-1)\n```\n\nA better solution with `O(n)` iterative deserialization:\n\n```\nclass Codec:\n\n    def serialize(self, root):\n        """Encodes a tree to a single string.\n        \n        :type root: TreeNode\n        :rtype: str\n        """\n        def dfs(root):\n            if not root:\n                return \n            res.append(str(root.val) + ",")\n            dfs(root.left)\n            dfs(root.right)\n            \n        res = []\n        dfs(root)\n        return "".join(res)\n\n    def deserialize(self, data):\n        """Decodes your encoded data to tree.\n        \n        :type data: str\n        :rtype: TreeNode\n        """\n        lst = data.split(",")\n        lst.pop()\n        stack = []\n        head = None\n        for n in lst:\n            n = int(n)\n            if not head:\n                head = TreeNode(n)\n                stack.append(head)\n            else:\n                node = TreeNode(n)\n                if n < stack[-1].val:\n                    stack[-1].left = node\n                else:\n                    while stack and stack[-1].val < n: \n                        u = stack.pop()\n                    u.right = node\n                stack.append(node)\n        return head\n```
[]