Python O(n) sol by pre-order traversal. 75%+ [ With explanation ]
Python O(n) sol by pre-order traversal.\n\n---\n\nHint:\n1. Pre-order traversal of binary search tree is unique and only. (i.e., no repetition between two diffe
Python O(n) sol by pre-order traversal.\n\n---\n\nHint:\n1. Pre-order traversal of binary search tree is **unique and only**. (i.e., no repetition between two different BSTs)\n\n2. **Pre-order traversal rule** of binary search tree is ( **current node, left-child, right-child**)\n\n3. Left child value < current node value < Right child value **if all elements are unique**.\n\n---\n\nAlgorithm:\n\nSerialization: \nGenerate a string to represent the input BST with preorder traversal.\n\nDeseialization:\nDecode the serialization string to rebuild BST by preorder traversal.\n\n---\n\nExample illustration\n\n---\n\nSerialization:\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1581313601.png)\n\n---\n\nDeserialization:\n\n![image](https://assets.leetcode.com/users/brianchiang_tw/image_1581313629.png)\n\n---\n\n```\nfrom collections import deque\nclass Codec:\n\n    def serialize(self, root: TreeNode) -> str:\n        """Encodes a tree to a single string.\n        """\n        \n        # record of preorder traversal path\n        path_of_preorder = []\n        \n        # Generate pre-order traversal path of binary search tree\n        def helper( node ):\n            \n            if node:\n                path_of_preorder.append( node.val )\n                helper( node.left )\n                helper( node.right )\n        \n        # ---------------------------------------------\n        helper( root )\n        # output as string, each node is separated by \'#\'\n        return \'#\'.join( map(str, path_of_preorder) )\n                \n        \n        \n\n    def deserialize(self, data: str) -> TreeNode:\n        """Decodes your encoded data to tree.\n        """\n        if not data:\n            # corner case handle for empty tree\n            return None\n        \n        # convert input string into doubly linked list of integer type, each node is separated by \'#\'\n        node_values = deque(  int(value) for value in data.split(\'#\') )\n        \n        # Reconstruct binary search tree by pre-order traversal\n        def helper( lower_bound, upper_bound):\n            \n            if node_values and lower_bound < node_values[0] < upper_bound:\n                \n                root_value = node_values.popleft()\n                root_node = TreeNode( root_value )\n                \n                root_node.left = helper( lower_bound, root_value )\n                root_node.right = helper( root_value, upper_bound )\n                \n                return root_node\n        \n        # ---------------------------------------------\n        \n        return helper( float(\'-inf\'), float(\'inf\'))    \n```\n\n---\n\nRelative leetcode challenge:\n[Leetcode #1008 Construct Binary Search Tree from Preorder Traversal](https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/)\n\n[Leetcode #144 Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)
['String', 'Python']