LeetCode #449 Serialize and Deserialize BST
Problem
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Solution
Use preorder to serialize nodes. Hence we know first element will be root and rest elements whose value are less than root are belong to left subtree and vice versa. Take recursive approach to construct the tree back.
Complexity
Preorder traversal takes O(n) time to visit each node once, where n denotes to count of nodes in this tree. So serialize takes O(n) time. And because it uses a stack to down to the leaves of left subtrees, its space complexity is O(h), where h denotes to tree height. Or O(logn) because h is bounded by logn.
For deserialize, it divides data into n parts by recursion. So its time is O(n) in best case because line 50 always executes once. But it may become O(n²) in worst case if rightStart in line 50 always reaches rightBound. For space complexity, it’s obviously O(n) because of n recursions at most.
