2 concise Java Solutions (O(n) and O(n2)) with using BST's feature (Not the old generic solution for Binary Tree)
Idea:\nWe are given a BST, so it is possible to reconstruct the tree by using Pre-Order traverse array.\n\nNotice we have 1 requirement "The encoded string shou
**Idea:**\nWe are given a BST, so it is possible to **reconstruct the tree by using Pre-Order traverse array**.\n\n*Notice we have 1 requirement "The encoded string should be as compact as possible." So let us forget the generic BFS/DFS solution for Binary Tree (Adding "#" or "NULL" for empty node)*\n\n\nSerialize:\nVery straightforward, simplify do a pre-order traverse and append to String.\n\n* Version 1: Two lines\n```\n    public String serialize(TreeNode root) {\n        if (root == null) return "";\n        return root.val + "," + serialize(root.left) + serialize(root.right);\n    }\n```\n\n* Version 2: Use StringBuilder to save a little bit time.\n```\n    public String serialize(TreeNode root) {\n        if (root == null) return "";\n        StringBuilder sb = new StringBuilder();\n        sb.append(root.val).append(",");\n        sb.append(serialize(root.left));\n        sb.append(serialize(root.right));\n        return sb.toString();\n    }\n```\n\nDeserialize\nSince we have a pre-order array. We always know the **first element is the root**. \nSo our strategy is to cut the array into different parts by appyling BST feature.\n\n* Version 1:  O(N2)\n1.Passing start bound and end bound to helper function, which means to reconstruct tree in this scope (start ~ end).\n2.Find the first element larger than current root, the first element index will be the middle cutting point. Which means all elements left to it need to be the **root.left**, all elements right after it need to be **root.right**. Recursively call the helper function.\n```\n    public TreeNode deserialize(String data) {\n        if (data == null || data.length() == 0) return null;\n        String[] sArr = data.split(",");\n        return helper(sArr, 0, sArr.length - 1);\n    }\n    \n    public TreeNode helper(String[] sArr, int start, int end) {\n        if (start > end) return null;\n        if (start == end) return new TreeNode(Integer.parseInt(sArr[start]));\n        TreeNode node = new TreeNode(Integer.parseInt(sArr[start]));\n        int mid = start + 1;\n        while (mid <= end) {\n            if (Integer.parseInt(sArr[mid]) > Integer.parseInt(sArr[start])) {\n                break;\n            }\n            mid++;\n        }\n        node.left = helper(sArr, start + 1, mid - 1);\n        node.right = helper(sArr, mid, end);\n        return node;\n    }\n```\n\n\n* Version 2: O(N)\n1.Similar id to @cccrrryyy 's solution: https://discuss.leetcode.com/topic/66495/using-lower-bound-and-upper-bound-to-deserialize-bst\n2.Pass a **min value (low bound)** and a **max value (high bound)** to helper function. \n3.I use **int[] currIdx** to simulate a static index variable, cuz I really don't  like using a static/member/global variable.\n```\n    public TreeNode deserialize(String data) {\n        if (data == null || data.length() == 0) return null;\n        String[] sArr = data.split(",");\n        int[] currIdx = {0};\n        return helper(sArr, currIdx, Integer.MIN_VALUE, Integer.MAX_VALUE);\n    }\n    \n    public TreeNode helper(String[] sArr, int[] currIdx, int min, int max) {\n        if (currIdx[0] > sArr.length - 1) return null;\n        int curr = Integer.parseInt(sArr[currIdx[0]]);\n\n        if (curr < min || curr > max) return null;\n\n        TreeNode node = new TreeNode(curr);\n        currIdx[0]++;\n        node.left = helper(sArr, currIdx, min, curr);\n        node.right = helper(sArr, currIdx, curr, max);\n        return node;\n\n    }
[]