LeetCode //C - 449. Serialize and Deserialize BST

449. Serialize and Deserialize BST

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.

Example 1:

Example 2:

Constraints:

The number of nodes in the tree is in the range [ 0 , 1 0 4 ] [0, 10^4] [0,104].
0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104
The input tree is guaranteed to be a binary search tree.

From: LeetCode
Link: 449. Serialize and Deserialize BST

Solution:

Ideas:

1. Serialization:

We use preorder traversal (root, left, right) to create a single string representation.
Each node’s value is added to the string, separated by spaces, which allows us to retrieve values easily during deserialization.

2. Deserialization:

We rebuild the tree by reading values from the serialized string.
We use the BST property by setting bounds for each recursive call to ensure that the value falls within the allowed range for a valid BST.
buildTree(lower, upper) ensures that values are correctly placed in the BST structure.

Code:

// Helper function to create a new tree node
struct TreeNode* newNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/** Encodes a tree to a single string. */
char* serialize(struct TreeNode* root) {
    // Buffer to hold the serialized data
    char* result = (char*)malloc(100000 * sizeof(char));
    int pos = 0;

    // Helper function to perform preorder traversal and serialize the tree
    void preorder(struct TreeNode* node) {
        if (!node) return;
        pos += sprintf(result + pos, "%d ", node->val); // Write value with space separator
        preorder(node->left);
        preorder(node->right);
    }

    preorder(root);
    result[pos] = '\0'; // Null-terminate the string
    return result;
}

/** Decodes your encoded data to tree. */
struct TreeNode* deserialize(char* data) {
    // Pointer to read values from the data
    int pos = 0;

    // Helper function to construct BST from preorder traversal using bounds
    struct TreeNode* buildTree(int lower, int upper) {
        if (!data[pos]) return NULL;

        int val;
        sscanf(data + pos, "%d", &val); // Read integer from data
        if (val < lower || val > upper) return NULL;

        // Move position to next integer
        while (data[pos] && data[pos] != ' ') pos++;
        if (data[pos] == ' ') pos++;
        
        struct TreeNode* node = newNode(val);
        node->left = buildTree(lower, val);
        node->right = buildTree(val, upper);
        return node;
    }

    return buildTree(INT_MIN, INT_MAX);
}

// Your functions will be called as such:
// char* data = serialize(root);
// struct TreeNode* root = deserialize(data);

Navigator_Z