# 449. Serialize and Deserialize 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 an algorithm to serialize and deserialize a **binary search tree**. There is no restriction on how your serialization/deserialization algorithm should work. You just 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.**

**Note:** Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

{% hint style="info" %}
利用到BST的性質的話就不需要給null node用特殊字符代替。
{% endhint %}

```cpp
// DFS Pre-Order Traversal
// Preorder Serialization Helper
void serialize(TreeNode* node, ostringstream& os) {
    if (!node) return;
    os << to_string(node->val) << " ";
    serialize(node->left, os);
    serialize(node->right, os);
}

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    ostringstream os;
    serialize(root, os);
    return os.str();
}

// Preorder Deserialization Helper
TreeNode* deserialize(istringstream& is, int lower, int upper) {
    streampos orig_pos = is.tellg(); // get the current output position in stringstream
    string cur;
    is >> cur;
    if (cur.empty()) return nullptr;
    int val = stoi(cur);
    if (val < lower || val > upper) {
        is.seekg(orig_pos); // reset pos in stringstream 
        return nullptr;
    } 
    TreeNode* root = new TreeNode(val);
    root->left = deserialize(is, lower, val);
    root->right = deserialize(is, val, upper);
    return root;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.empty()) return nullptr;
    istringstream is(data);
    return deserialize(is, INT_MIN, INT_MAX);
}
```

```cpp
// DFS Pre-Order Traversal
// Preorder Serialization Helper
void serialize(TreeNode* node, ostringstream& os) {
    if (!node) os << "# ";
    else {
        os << to_string(node->val) << " ";
        serialize(node->left, os);
        serialize(node->right, os);
    }
}

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    ostringstream os;
    serialize(root, os);
    return os.str();
}

// Preorder Deserialization Helper
TreeNode* deserialize(istringstream& is) {
    string val;
    is >> val;
    if (val == "#") return nullptr;
    TreeNode* root = new TreeNode(stoi(val));
    root->left = deserialize(is);
    root->right = deserialize(is);
    return root;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    istringstream is(data);
    return deserialize(is);
}
```

```cpp
// BFS Level Order Traversal
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    if (!root) return "";
    ostringstream os;
    queue<TreeNode*> q({root});
    while (!q.empty()) {
        TreeNode* t = q.front(); q.pop();
        if (!t) {
            os << "# ";
        } else {
            os << to_string(t->val) << " ";
            q.push(t->left);
            q.push(t->right);
        }
    }
    return os.str();
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.empty()) return nullptr;
    istringstream is(data);
    queue<TreeNode*> q;
    string val;
    is >> val;
    TreeNode* res = new TreeNode(stoi(val)), *cur = res;
    q.push(cur);
    while (!q.empty()) {
        TreeNode* t = q.front(); q.pop();
        if (!(is >> val)) break;
        if (val != "#") {
            cur = new TreeNode(stoi(val));
            q.push(cur);
            t->left = cur;
        }
        if (!(is >> val)) break;
        if (val != "#") {
            cur = new TreeNode(stoi(val));
            q.push(cur);
            t->right = cur;
        }
    }
    return res;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/449.-serialize-and-deserialize-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.