Java PreOrder + Queue solution
Hi all, I think my solution is pretty straightforward and easy to understand, not that efficient though. And the serialized tree is compact.\nPre order traversa
Hi all, I think my solution is pretty straightforward and easy to understand, not that efficient though. And the serialized tree is compact.\nPre order traversal of BST will output root node first, then left children, then right.\n```\nroot left1 left2 leftX right1 rightX\n```\nIf we look at the value of the pre-order traversal we get this:\n```\nrootValue (<rootValue) (<rootValue) (<rootValue) |separate line| (>rootValue) (>rootValue)\n```\nBecause of BST's property: before the |separate line| all the node values are **less than root value**, all the node values after |separate line| are **greater than root value**. We will utilize this to build left and right tree.\n\nPre-order traversal is BST's serialized string. I am doing it iteratively.\nTo deserialized it, use a queue to recursively get root node, left subtree and right subtree.\n\n\nI think time complexity is O(NlogN).\nErrr, my bad, as @ray050899 put below, worst case complexity should be O(N^2), when the tree is really unbalanced. \n\n\nMy implementation\n```\npublic class Codec {\n    private static final String SEP = ",";\n    private static final String NULL = "null";\n    // Encodes a tree to a single string.\n    public String serialize(TreeNode root) {\n        StringBuilder sb = new StringBuilder();\n        if (root == null) return NULL;\n        //traverse it recursively if you want to, I am doing it iteratively here\n        Stack<TreeNode> st = new Stack<>();\n        st.push(root);\n        while (!st.empty()) {\n            root = st.pop();\n            sb.append(root.val).append(SEP);\n            if (root.right != null) st.push(root.right);\n            if (root.left != null) st.push(root.left);\n        }\n        return sb.toString();\n    }\n\n    // Decodes your encoded data to tree.\n    // pre-order traversal\n    public TreeNode deserialize(String data) {\n        if (data.equals(NULL)) return null;\n        String[] strs = data.split(SEP);\n        Queue<Integer> q = new LinkedList<>();\n        for (String e : strs) {\n            q.offer(Integer.parseInt(e));\n        }\n        return getNode(q);\n    }\n    \n    // some notes:\n    //   5\n    //  3 6\n    // 2   7\n    private TreeNode getNode(Queue<Integer> q) { //q: 5,3,2,6,7\n        if (q.isEmpty()) return null;\n        TreeNode root = new TreeNode(q.poll());//root (5)\n        Queue<Integer> samllerQueue = new LinkedList<>();\n        while (!q.isEmpty() && q.peek() < root.val) {\n            samllerQueue.offer(q.poll());\n        }\n        //smallerQueue : 3,2   storing elements smaller than 5 (root)\n        root.left = getNode(samllerQueue);\n        //q: 6,7   storing elements bigger than 5 (root)\n        root.right = getNode(q);\n        return root;\n    }\n}\n```
[]