Serialize and Deserialize BST

This approach treats the Binary Search Tree as a general Binary Tree. It serializes the tree using a pre-order traversal, explicitly storing null children with a special marker (e.g., 'N' or '#'). This ensures that the structure can be perfectly reconstructed, but it doesn't take advantage of the BST properties, leading to a less compact string as requested by the problem.

• Serialization:
  1. Define a recursive function serializeHelper(node, stringBuilder).
  2. If node is null, append a null marker (e.g., "N") and a separator to the stringBuilder and return.
  3. Otherwise, append the node.val and a separator.
  4. Recursively call serializeHelper for the left child.
  5. Recursively call serializeHelper for the right child.
• Deserialization:
  1. Split the input string by the separator into a queue of strings.
  2. Define a recursive function deserializeHelper(queue).
  3. Dequeue a value from the queue.
  4. If the value is the null marker, return null.
  5. Otherwise, create a new TreeNode with the parsed value.
  6. Set the node's left child by recursively calling deserializeHelper(queue).
  7. Set the node's right child by recursively calling deserializeHelper(queue).
  8. Return the created node.

Serialization

A recursive Depth-First Search (DFS) function, specifically pre-order, is used. The function traverses the tree in the order: root -> left -> right. When a non-null node is encountered, its value is appended to a string builder, followed by a delimiter. When a null pointer is encountered (an empty child), a special marker (e.g., "N") is appended. This process creates a string that uniquely represents the tree structure, including its empty branches.

Deserialization

The serialized string is first split by the delimiter into a list of values. A queue is a natural choice to process these values in the order they were generated. A recursive helper function builds the tree. It dequeues the next value. If the value is the null marker, it returns null. Otherwise, it creates a new node with the parsed integer value. It then recursively calls itself to build the left subtree and then the right subtree, perfectly reconstructing the original tree.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "N";

    // 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 node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP);
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(SEP)));
        return deserializeHelper(nodes);
    }

    private TreeNode deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals(NULL)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(nodes);
        node.right = deserializeHelper(nodes);
        return node;
    }
}