[Python] O(n) solution, using preorder traversal, explained
My idea to solve this problem is to use Problem 1008. Construct Binary Search Tree from Preorder Traversal. So:\n\n1. For our serialization we just get preorder
My idea to solve this problem is to use **Problem 1008**. Construct Binary Search Tree from Preorder Traversal. So:\n\n1. For our serialization we just get preorder traversel (iterative or recursion, whatever you want, I used iterative, using stack).\n2. For deserialization we use solution with `O(n)` time complexity: we give the function two bounds - `up` and `down`: the maximum number it will handle. The left recursion will take the elements smaller than `node.val` and  the right recursion will take the remaining elements smaller than `bound`.\n\n**Complexity**: both for serialization and deserialization is `O(n)`, because `self.index` will be increased by one on each iteration.\n\n```\nclass Codec:\n    def serialize(self, root):\n        if not root: return ""\n        stack, out = [root], []\n        while stack:\n            cur = stack.pop()\n            out.append(cur.val)\n            for child in filter(None, [cur.right, cur.left]):\n                stack += [child]\n                \n        return \' \'.join(map(str, out))\n        \n    def deserialize(self, data):\n        preorder = [int(i) for i in data.split()]\n        def helper(down, up):\n            if self.idx >= len(preorder): return None\n            if not down <= preorder[self.idx] <= up: return None\n            root = TreeNode(preorder[self.idx])\n            self.idx += 1\n            root.left = helper(down, root.val)\n            root.right = helper(root.val, up)\n            return root\n            \n        self.idx = 0\n        return helper(-float("inf"), float("inf"))\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]