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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Serialize and Deserialize BST

Number: 449

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon

Problem Description

Serialize and Deserialize a Binary Search Tree (BST). Design an algorithm to convert a given BST into a compact string representation and reconstruct the BST from that string. The encoded string should be as compact as possible, and the input tree is guaranteed to be a valid BST.

Key Insights

  • Use preorder traversal for serialization: record the root first, then the left and right subtrees.
  • Leverage BST properties: all nodes in the left subtree are less than the root, and all nodes in the right subtree are greater.
  • During deserialization, maintain lower and upper bounds for valid node values to correctly reconstruct the tree without extra markers.
  • This approach yields a compact representation as it does not need to represent null children explicitly.

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) due to the recursion stack and storage of the serialized string.

Solution

The solution serializes the BST using a preorder traversal, outputting node values separated by spaces. For deserialization, the preorder values are processed recursively by enforcing BST property bounds. A pointer (or index) moves through the serialized value list, ensuring that each value fits within the expected lower and upper limits for its position in the tree. This method avoids the use of null markers, resulting in a compact string representation.

Code Solutions

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

class Codec:
    def serialize(self, root):
        # Preorder traversal to serialize the BST.
        def preorder(node):
            if not node:
                return []
            return [str(node.val)] + preorder(node.left) + preorder(node.right)
        # Join the values with a space for a compact representation.
        return " ".join(preorder(root))
    
    def deserialize(self, data):
        if not data:
            return None
        
        # Convert the input string into a list of integers.
        preorder_values = [int(val) for val in data.split()]
        self.index = 0
        
        # Helper function to reconstruct BST using valid bounds.
        def buildBST(lower, upper):
            if self.index == len(preorder_values):
                return None
            val = preorder_values[self.index]
            if val < lower or val > upper:
                return None
            
            self.index += 1
            node = TreeNode(val)
            node.left = buildBST(lower, val)
            node.right = buildBST(val, upper)
            return node
        
        return buildBST(float('-inf'), float('inf'))
← Back to All Questions