Serialize and Deserialize BST is the top interview coding question asked in Amazon, Facebook, Google, and Netflix. Today we will be discussing the algorithm required to solve this question. So, First, let see the question first.
Serialization is 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 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.
Python Solution as Submitted to LeetCode:
So, the logic is to serialize the existing BST using Pre-Order Traversal so that the first node is the root, and then we are using re-constructing the BST using the insert function which checks the root node and adjusts the tree accordingly.
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: preOrderString = "" def getPreOrder(self, root: TreeNode): if root == None: return self.preOrderString = self.preOrderString + str(root.val) + " " self.getPreOrder(root.left) self.getPreOrder(root.right) def serialize(self, root: TreeNode) -> str: """Encodes a tree to a single string. """ self.getPreOrder(root) return self.preOrderString def deserialize(self, data: str) -> TreeNode: """Decodes your encoded data to tree. """ if not data: return None dataList = data.strip().split(" ") root = TreeNode(int(dataList)) def insert(node, value): if not node: return TreeNode(value) if node.val>value: node.left = insert(node.left, value) else: node.right = insert(node.right, value) return node for i in range(1, len(dataList)): root = insert(root, int(dataList[i].strip())) return root # Your Codec object will be instantiated and called as such: # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # tree = ser.serialize(root) # ans = deser.deserialize(tree) # return ans
Preorder Traversal takes O(n) where n is a number of elements in BST. Also, since it uses the list to store the data to the height h, therefore, the Space Complexity is O(h), where h denotes tree height.
For deserialization, the time complexity is O(n) best case and O(n2) for the worst case. Also, the space complexity is O(n).
This question can be found on the majority of the algorithm-related websites such as Hackerrank, Interviewbit, and LeetCode.
Wanna read more interview-related questions? Check Top Interview Questions category.