Serialize and Deserialize BST

Problem Statement

In computer science, serialization involves converting a data structure or object into a sequence of bits to facilitate storage in a file, memory buffer, or to transmit across a network so that it can be reconstructed later in the same or another computing environment. In the context of this problem, the goal is to develop an algorithm capable of both serializing and deserializing a binary search tree (BST). Serialization should transform the BST into a compact string form while deserialization should revert this string back into the original BST structure. The design of the algorithm is not restricted, but the solution should emphasize achieving the most compact string representation possible.

Examples

Example 1

Input:

root = [2,1,3]

Output:

[2,1,3]

Example 2

Input:

root = []

Output:

[]

Constraints

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The input tree is guaranteed to be a binary search tree.

Approach and Intuition

Given that the purpose is to serialize and deserialize a binary search tree, let's delve into a typical approach and intuition:

1. Understanding Binary Search Trees (BSTs):

   • BSTs have the property where the left child node's value is less than the parent node's value and the right child node's value is greater. This property is pivotal because it ensures that each element in the tree is uniquely placed based on its value.

2. Serialization Approach:

   • To serialize the BST, you can use several methods, such as pre-order, in-order, post-order traversal, or level-order traversal. However, for reconstructing the BST exactly, using pre-order or post-order traversal is often the most straightforward approach because these methods record the root's position early.
   • In pre-order traversal, the root is processed before the left and right subtrees, which helps in maintaining the hierarchy of the tree during deserialization.
   • A compact form of serialization can be achieved by separating node values with a delimiter, like commas, and using a specific character, such as 'N', to denote null values (empty nodes).

3. Deserialization Approach:

   • Deserialization involves reconstructing the BST from the serialized string. If pre-order traversal was used for serialization, the string can be split by its delimiters, and a recursive function can be employed that takes the list of node values (and indices for bounds) to recreate the tree.
   • Given that we know the properties of BST and have the root value (from the serialized string's starting value in the case of pre-order serialization), the tree can be recursively rebuilt by inserting nodes such that they retain the BST properties.

Using the examples provided as a reference:

• Example 1:

  • The BST with root as [2,1,3] when serialized may look like 2,1,3 using pre-order.
  • Deserialization would involve reading 2 as root, placing 1 on the left of 2, and 3 on the right, correctly reconstructing the tree.

• Example 2:

  • An empty tree [] would straightforwardly serialize to an empty string and vice versa.

Constraints ensure that node values and the count are within manageable limits and the architecture operates within these defined parameters, guaranteeing a BST as input for correct functionality.

Solutions

public class TreeCodec {
    public void encodeTree(TreeNode node, StringBuilder output) {
        if (node == null)
            return;
        encodeTree(node.left, output);
        encodeTree(node.right, output);
        output.append(convertIntToString(node.val));
    }
    
    public String convertIntToString(int number) {
        char[] characters = new char[4];
        for (int i = 3; i >= 0; i--) {
            characters[3 - i] = (char) ((number >> (i * 8)) & 0xFF);
        }
        return new String(characters);
    }
    
    public String createSerializedData(TreeNode node) {
        StringBuilder serializedData = new StringBuilder();
        encodeTree(node, serializedData);
        return serializedData.toString();
    }
    
    public TreeNode buildTreeFromList(Integer lowerBound, Integer upperBound, ArrayDeque<Integer> numbers) {
        if (numbers.isEmpty())
            return null;
        int value = numbers.getLast();
        if (value < lowerBound || value > upperBound)
            return null;
    
        numbers.removeLast();
        TreeNode rootNode = new TreeNode(value);
        rootNode.right = buildTreeFromList(value, upperBound, numbers);
        rootNode.left = buildTreeFromList(lowerBound, value, numbers);
        return rootNode;
    }
    
    public int parseStringToInt(String valueStr) {
        int parsedValue = 0;
        for (char b : valueStr.toCharArray()) {
            parsedValue = (parsedValue << 8) + (int) b;
        }
        return parsedValue;
    }
    
    public TreeNode decodeStringToTree(String encodedData) {
        ArrayDeque<Integer> integerValues = new ArrayDeque<Integer>();
        int size = encodedData.length();
        for (int i = 0; i < size / 4; i++) {
            integerValues.add(parseStringToInt(encodedData.substring(4 * i, 4 * i + 4)));
        }
    
        return buildTreeFromList(Integer.MIN_VALUE, Integer.MAX_VALUE, integerValues);
    }
}