We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Serialize and Deserialize BST

Difficulty: Medium

Problem Description

Design an algorithm to serialize and deserialize a binary search tree. Ensure that a binary search tree can be serialized to a string and that this string can be deserialized to the original tree structure. The encoded string should be as compact as possible.

Key Insights

  • Serialization involves converting the tree structure into a string representation.
  • Deserialization involves reconstructing the tree from the string representation.
  • A binary search tree (BST) has the property that for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.
  • In-order traversal can be helpful for serialization since it preserves the BST properties.

Space and Time Complexity

Time Complexity: O(n) for both serialization and deserialization, where n is the number of nodes in the tree.
Space Complexity: O(n) for storing the serialized string and the call stack in the worst case during tree traversal.

Solution

To serialize the BST, we can perform a pre-order traversal where we visit the root node first, then recursively serialize the left subtree followed by the right subtree. This will create a string that retains the structure of the tree.

For deserialization, we can split the serialized string and reconstruct the BST by inserting each value into the tree while maintaining the BST properties.

The approach uses a recursive depth-first search (DFS) strategy to traverse and reconstruct the tree.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string."""
        def helper(node):
            if not node:
                return "null,"
            return str(node.val) + "," + helper(node.left) + helper(node.right)
        
        return helper(root)

    def deserialize(self, data):
        """Decodes your encoded data to tree."""
        def helper(nodes):
            val = next(nodes)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = helper(nodes)
            node.right = helper(nodes)
            return node
        
        return helper(iter(data.split(',')))

# Example usage:
# codec = Codec()
# tree_string = codec.serialize(root)
# root = codec.deserialize(tree_string)
← Back to All Questions