# 449. Serialize and Deserialize BST
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
Approach 1: We can reconstruct BST from preorder traversal alone because you can separate the left and right subtree by comparing values with the root. To deserialize, search through the serialization (linearly) to cut the left and right subtree. Average case O(NlogN)
, worse case O(N^2)
.
Approach 2: Deserialize smartly in O(N)
. This can be done by recursing through the serialization, setting upper and lower bounds for each subtree.
# Code (Python)
Approach 1:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
# can reconstruct BST from preorder traversal alone because you can separate the left and right subtree by comparing values with the root
if not root:
return ''
result = [str(root.val)]
if root.left:
result.append(self.serialize(root.left))
if root.right:
result.append(self.serialize(root.right))
return ','.join(result)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
preorder = list(map(int, data.split(',')))
return self._reconstruct(preorder, 0, len(preorder) - 1)
def _reconstruct(self, preorder, start, end):
# best case: T(N) = 2T(N/2) + O(N) --> O(NlogN)
# worse case: T(N) = T(N-1) + N + T(N-2) + N + ... --> O(N^2)
if not preorder or start > end:
return None
if start == end:
return TreeNode(preorder[start])
root = TreeNode(preorder[start])
right_start = start + 1
while right_start <= end and preorder[right_start] < preorder[start]:
right_start += 1
root.left = self._reconstruct(preorder, start + 1, right_start - 1)
root.right = self._reconstruct(preorder, right_start, end)
return root
Approach 2:
Same thing for serialize()
.
def deserialize(self, data):
# use lower and upper bound to recursively limit tree construction -- each item gets popped from the queue once as the recursion goes down
# time: O(N)
if not data:
return None
preorder = deque(map(int, data.split(',')))
return self._construct(preorder, -float('inf'), float('inf'))
def _construct(self, preorder, low, high):
if preorder and low < preorder[0] < high:
root = TreeNode(preorder.popleft())
root.left = self._construct(preorder, low, root.val)
root.right = self._construct(preorder, root.val, high)
return root
else:
return None # for upcoming nodes in the queue that are out of boundary (should be under another subtree)
# Code (C++)
Approach 1:
Approach 2: