Java O(n) Iterative, no nulls
The whole point of this question is to use the BST property to at get rid of nulls in your serialized string (Question #297). Anything less is a suboptimal solu
The whole point of this question is to use the BST property to at get rid of nulls in your serialized string (Question #297). Anything less is a suboptimal solution.\n\n  - To Serialize just do an iterative pre-order traversal. (in real world, recursive can stack overflow if BST is unbalanced)\n  - To Deserialize:\n\t  - if next node is smaller then parent just (left) add to parent.\n\t  - if next node is larger then parent pop the stack until you find the largest parent you can (right) add to.\n\t  - finally stack the next node as a candidate parent.\n\nEach node gets in and out of stack only once, so time complexity `O(n)`, and the serialized string has no nulls, or markers only the nodes.\n\n```java\n    public String serialize(TreeNode n) {\n        if (n == null) return "";\n        StringBuilder sb = new StringBuilder();\n        \n        Stack<TreeNode> stack = new Stack<>();\n        while (n!=null) {\n            sb.append(n.val).append(",");\n            if (n.right != null) stack.push(n.right);\n            n = (n.left == null && !stack.isEmpty()) ? stack.pop() : n.left;\n        }\n        sb.setLength(sb.length()-1);\n        return sb.toString();\n    }\n\n    public TreeNode deserialize(String s) {\n        if ("".equals(s)) return null;\n        String[] tokens = s.split(",");\n        \n        Stack<TreeNode> stack = new Stack<>();\n        TreeNode head = new TreeNode(Integer.valueOf(tokens[0]));\n        stack.push(head);\n        \n        for (int i=1;i<tokens.length;i++) {\n            \n            TreeNode parent = stack.peek();\n            TreeNode next = new TreeNode(Integer.valueOf(tokens[i]));\n            \n            if (next.val < parent.val) parent.left = next;\n            else {\n                parent = stack.pop();\n                while (!stack.isEmpty() && next.val > stack.peek().val) parent = stack.pop();\n                parent.right = next;\n            }\n            stack.push(next);\n        }\n        return head;\n    }\n```
[]