Serialize and Deserialize Binary Search Tree BST

Problem

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.

The encoded string should be as compact as possible.

Examples

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

This is what we have to implement:

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
    }
}

Solution

We have already seen - [Serialize and Deserialize Binary Tree](serialize-and-deserialize-binary-tree). So, we can use BFS or Preorder DFS to encode and decode.

Method 1 - BFS or Level Order Traversal with # as Delimiter

Refer [Serialize and Deserialize Binary Tree](serialize-and-deserialize-binary-tree)

Method 2 - Preorder DFS

This is similar to approach here: [Serialize and Deserialize Binary Tree](serialize-and-deserialize-binary-tree).

Use upper and lower boundaries to check whether we should add null. To solve this problem, we will use Preorder Traversal for serialization. Preorder traversal processes the root node first, followed by the left subtree and then right subtree. This is ideal for reconstructing the binary search tree because we can split the values into left and right subtrees based on the BST property.

Steps for Serialization

1. Traverse the tree with Preorder traversal.
2. Append the values of nodes to a string, separated by a delimiter (e.g., comma ,).
3. Convert this list into a compact string.

Steps for Deserialization

1. Split the serialized string into a list of integers.
2. Reconstruct the BST recursively using the range constraints of BST properties: Left subtree values < root, Right subtree values > root.

Reasoning

• Compactness is achieved using Preorder traversal since it retains the BST structure while using a single traversal result.
• Reconstructing the BST leverages the ordered nature of Preorder traversal combined with range constraints.

Code

Java

class Solution {

    // Definition for a binary tree node
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) {
            this.val = val;
        }
    }
    
    // Serialize the BST
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) return;
        sb.append(node.val).append(','); // Append current node's value
        serializeHelper(node.left, sb); // Process left subtree
        serializeHelper(node.right, sb); // Process right subtree
    }

    // Deserialize the BST
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] values = data.split(",");
        return deserializeHelper(values, 0, values.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode deserializeHelper(String[] values, int start, int end, int min, int max) {
        if (start > end) return null;
        int val = Integer.parseInt(values[start]);
        if (val < min || val > max) return null; // Value out of range
        
        TreeNode root = new TreeNode(val);
        int idx = start + 1;
        while (idx <= end && Integer.parseInt(values[idx]) < val) idx++; // Split left and right subtrees
        
        root.left = deserializeHelper(values, start + 1, idx - 1, min, val); // Left subtree
        root.right = deserializeHelper(values, idx, end, val, max); // Right subtree
        
        return root;
    }
}

Python

class Solution:
    # Serialize the BST
    def serialize(self, root: Optional[TreeNode]) -> str:
        ans: List[str] = []
        self._serialize_helper(root, ans)
        return ",".join(ans)
    
    def _serialize_helper(self, node: Optional[TreeNode], ans: List[str]) -> None:
        if node:
            ans.append(str(node.val))  # Append current node's value
            self._serialize_helper(node.left, ans)  # Process left subtree
            self._serialize_helper(node.right, ans) # Process right subtree

    # Deserialize the BST
    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        values = list(map(int, data.split(",")))  # Convert string to list of integers
        return self._deserialize_helper(values, float("-inf"), float("inf"))
    
    def _deserialize_helper(self, values: List[int], min_val: float, max_val: float) -> Optional[TreeNode]:
        if not values or values[0] < min_val or values[0] > max_val:
            return None
        val = values.pop(0)  # Pop the first value
        root = TreeNode(val)
        root.left = self._deserialize_helper(values, min_val, val)  # Left subtree
        root.right = self._deserialize_helper(values, val, max_val) # Right subtree
        return root

Complexity

• ⏰ Time complexity: 
  • Serialization: Traversal takes O(n) where n is the number of nodes in the BST.
  • Deserialization: Reconstruction also takes O(n) because each node is processed exactly once.
• 🧺 Space complexity: O(n)
  • Serialization: O(n) for storing the serialized string.
  • Deserialization: O(n) for storing the list of integers and the recursive call stack during reconstruction.

Method 3 - Preorder with BST Limit Check

Code

Java

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }
    
    public void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {return;}
        sb.append(root.val).append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserialize(q, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    public TreeNode deserialize(Queue<String> q, int lower, int upper) {
        if (q.isEmpty()) return null;
        String s = q.peek();
        int val = Integer.parseInt(s);
        if (val < lower || val > upper) return null;
        q.poll();
        TreeNode root = new TreeNode(val);
        root.left = deserialize(q, lower, val);
        root.right = deserialize(q, val, upper);
        return root;
    }
}

We can make a single serialize method like this:

public void serialize(TreeNode root) {
	if (root == null) {return "" ;}
	StringBuilder sb = new StringBuilder();
	sb.append(root.val).append(",").append(serialize(root.left)).append()
	return sb.toString();
}