MANG Problem #36: Serialize and Deserialize BST (Hard)

1. Problem Statement

Serialization is converting a data structure to a sequence of bits. Design an algorithm to serialize and deserialize a Binary Search Tree (BST).

The encoded string should be as compact as possible.

2. Approach: Pre-order without Nulls

In a generic Binary Tree, we must store "Null markers" (X) to know when a branch ends. However, because this is a BST, the values themselves dictate the structure! If we serialize using Pre-order (Root, Left, Right), we can reconstruct the tree purely using upper and lower bounds.

1. Serialize: Standard Pre-order traversal. Join with commas. No nulls needed!
2. Deserialize: Read values from left to right. Maintain min and max bounds. If the next value in the string doesn't fit the bounds for the current node's child, it belongs to a different branch higher up.

3. Java Implementation

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }
    
    private void serializeHelper(TreeNode root, StringBuilder sb) {
        if (root == null) return;
        sb.append(root.val).append(",");
        serializeHelper(root.left, sb);
        serializeHelper(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 deserializeHelper(q, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private TreeNode deserializeHelper(Queue<String> q, int lower, int upper) {
        if (q.isEmpty()) return null;
        
        int val = Integer.parseInt(q.peek());
        // If value doesn't fit the BST property for this position, it belongs elsewhere
        if (val < lower || val > upper) return null;
        
        q.poll(); // Consume the value
        TreeNode root = new TreeNode(val);
        
        root.left = deserializeHelper(q, lower, val);
        root.right = deserializeHelper(q, val, upper);
        
        return root;
    }
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: A BST is self-organizing. If the string is 5, 3, 1, 4, 7, and I just created node 3, the bounds for its left child are (-∞, 3). The next number is 1. It fits! I make it the left child.
2. The Rejection: The next number is 4. I try to make it the left child of 1, but the bounds are (-∞, 1). It fails! The recursion naturally returns null, and passes 4 up to be the right child of 3, where the bounds are (3, 5). It fits!
3. Space Efficiency: We save roughly 50% of the string size by omitting null pointers.

5. Interview Discussion

• Interviewer: "Could we use Post-order?"
• You: "Yes, but we would have to read the string backwards from right to left during deserialization, because the root is at the end."
• Interviewer: "What about In-order?"
• You: "In-order serialization of a BST just gives a sorted array. You cannot uniquely reconstruct the original tree structure from just a sorted array."