algoadvance

Leetcode 449. Serialize and Deserialize BST

Problem Statement

You need to design algorithms to serialize and deserialize a binary search tree (BST). Serialization is the process of 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 algorithms:

1. string serialize(TreeNode* root) - Converts the BST to a single string.
2. TreeNode* deserialize(string data) - Converts the string back to the BST.

The encoded string should be as compact as possible.

Clarifying Questions

1. Input and Output Format:
   • Input: For the serialize function, input is the root of a BST. For the deserialize function, input is the string.
   • Output: For the serialize function, output is a string representation of the BST. For the deserialize function, output is the root of the BST.
2. Constraints:
   • The BST contains only integer values.
   • Duplicate nodes are not allowed in the BST.
   • The number of nodes in the BST is in the range [0, 10^4].

Strategy

• Serialization: Perform a preorder traversal of the BST and convert the nodes to a string separated by spaces. Preorder traversal captures the root node first, then the left subtree, followed by the right subtree. This helps in easily reconstructing the BST.

• Deserialization: Use the preorder traversal string to reconstruct the BST. The first value in the string will be the root of the BST. Use this value to recursively reconstruct the left and right subtrees by maintaining the range constraints of BST nodes.

Code

#include <string>
#include <sstream>
#include <vector>
#include <climits>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
public:
    // Function to serialize the BST to a string.
    string serialize(TreeNode* root) {
        // Use a stringstream to build the serialized string.
        stringstream ss;
        serializeHelper(root, ss);
        return ss.str();
    }

    // Function to deserialize the string to a BST.
    TreeNode* deserialize(string data) {
        // Create a stringstream from the data to easily extract node values.
        stringstream ss(data);
        vector<int> preorderValues;
        string value;
        while (getline(ss, value, ' ')) {
            if (!value.empty()) {
                preorderValues.push_back(stoi(value));
            }
        }
        int index = 0;
        return deserializeHelper(preorderValues, index, INT_MIN, INT_MAX);
    }

private:
    void serializeHelper(TreeNode* node, stringstream& ss) {
        if (!node) return;
        ss << node->val << " ";
        serializeHelper(node->left, ss);
        serializeHelper(node->right, ss);
    }

    TreeNode* deserializeHelper(const vector<int>& values, int& index, int minVal, int maxVal) {
        if (index >= values.size()) return nullptr;
        int value = values[index];
        if (value < minVal || value > maxVal) return nullptr;
        
        TreeNode* root = new TreeNode(value);
        index++; // Move to the next element
        
        root->left = deserializeHelper(values, index, minVal, value);
        root->right = deserializeHelper(values, index, value, maxVal);
        
        return root;
    }
};

Time Complexity

• Serialization:
  • Time Complexity: O(N), where N is the number of nodes in the BST. Each node is visited once during the preorder traversal.
  • Space Complexity: O(N), to store the string representation of the BST.
• Deserialization:
  • Time Complexity: O(N), where N is the number of nodes in the BST. The recursion visits each node once.
  • Space Complexity: O(N), for the recursion stack in the worst case (unbalanced tree). Extra space is also used to store the preorder values.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?