Serialize and Deserialize BST Solution

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.

Question:

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[0]))
        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

Complexity:

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(n²) 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.

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.