449.Serialize and Deserialize BST

Tags: [BST], [binary_tree], [postorder_traversal], [inorder_traversal], [serialization], [deserialization]

Link: https://leetcode.com/problems/serialize-and-deserialize-bst/?tab=Description

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 abinary 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: using postorder traversal sequence and inorder traversal sequence to build binary tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''

        preorder = []
        self.preorder_traverse(root, preorder)

        inorder = []
        self.inorder_traverse(root, inorder)
        return ','.join([str(node.val) for node in preorder]) + ',' + ','.join([str(node.val) for node in inorder])

    def preorder_traverse(self, root, rest):
        # base case
        if not root:
            return

        # root
        rest.append(root)
        # left
        self.preorder_traverse(root.left, rest)
        # right
        self.preorder_traverse(root.right, rest)

    def inorder_traverse(self, root, rest):
        # base case
        if not root:
            return

        # left
        self.inorder_traverse(root.left, rest)
        # root
        rest.append(root)
        # right
        self.inorder_traverse(root.right, rest)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None

        arr = [int(x) for x in data.split(',')]
        preorder = arr[:len(arr) / 2]
        inorder = arr[len(arr) / 2:]

        return self.build_tree(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)

    def build_tree(self, preorder, p_start, p_end, inorder, in_start, in_end):
        # base case
        if p_start < 0 or p_end >= len(preorder) or p_start > p_end or\
           in_start < 0 or in_end >= len(inorder) or in_start > in_end:
            return None

        root = TreeNode(preorder[p_start])

        root_index_in_inorder = inorder.index(root.val)
        num_of_nodes_left_sub_tree = root_index_in_inorder - in_start
        num_of_nodes_right_sub_tree = in_end - root_index_in_inorder

        left_sub_tree_p_start = p_start + 1
        left_sub_tree_p_end = left_sub_tree_p_start + num_of_nodes_left_sub_tree - 1
        right_sub_tree_p_start = left_sub_tree_p_end + 1
        right_sub_tree_p_end = p_end

        left_sub_tree_in_start = in_start
        left_sub_tree_in_end = root_index_in_inorder - 1
        right_sub_tree_in_start = root_index_in_inorder + 1
        right_sub_tree_in_end = in_end

        root.left = self.build_tree(preorder, left_sub_tree_p_start, left_sub_tree_p_end,
                                    inorder, left_sub_tree_in_start, left_sub_tree_in_end)
        root.right = self.build_tree(preorder, right_sub_tree_p_start, right_sub_tree_p_end,
                                     inorder, right_sub_tree_in_start, right_sub_tree_in_end)
        return root

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

Revelation:

• Use any two of preorder traversal, inorder traversal, and postorder traversal sequences can build (re-build) the binary tree.

Note:

• Serialization time complexity = O(n), n is the number of nodes in the given tree.
• Deserialization time complexity = O(n), n is the number of nodes in the given tree.
• Be careful of the base case of the above the recursion.

Question:

• Is the above algorithm still correct, if there exists duplicate nodes(value) in the binary tree. (BST allows duplicates nodes values).

Answer:

• The above algorithm(code) will generate errors, when there exists duplicate nodes(values) in the binary tree.