DAY 61 - Serialize and Deserialize Binary Tree
Tags: tutorial, algorithms, coding
Published: 2023-08-03 18:34:26

Welcome to DAY 61. Today we will diverge once again into the Data Structure Trees and look at some more questions. I suggest reading the previous articles that I have written on Trees before reading this.

---

## Question: [Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/)

_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 tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure._

_Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself._

---

### _Example 1:_

> ![Example](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pmjkhh1vebgdn2587ggn.png)


> - Input: root = [1,2,3,null,null,4,5]
> - Output: [1,2,3,null,null,4,5]

---

## Intuition:
- The question is pretty easy. We need to convert a binary tree into a string first and then write a function to convert it back to a tree.
- Let's see how we can solve this. To make a binary tree into a string, we can just do level order traversal and push the value into a string by using `to_string` function to convert it.
- We also add comma characters as separators so we can clearly differentiate between the values.
- We also use a special character to identify null nodes and pass them as '%' here.
- The hard part is deserialzing. So here we use a queue and push the first character of the string as it's obviously the root.
- Next we use the same approach but this time instead of doing lvl order traversal. We check if the current node is  '%'. So we know that the left of this node is a null.
- We do the same thing again to check for right. Remember level order traversal goes like bfs.
- Everytime we encounted that if it's not null we simply push it into queue and give it the appropriate parent.

---

## Algorithm and Code:
**_Serialize Function:_**

- The serialize function traverses the binary tree in level-order using a queue (BFS).
- It starts by pushing the root node into the queue.
- While the queue is not empty, it dequeues a node, appends its value to the result string followed by a comma (,).
- If the node is not NULL, it enqueues its left and right children into the queue.
- If the node is NULL, it appends %, to the result string to represent a NULL node.
- The resulting string represents the serialized binary tree.

**_Deserialize Function:_**

- The deserialize function takes the serialized string as input and reconstructs the binary tree.
- It first checks if the input string is empty, in which case it returns NULL (empty tree).
- It uses a stringstream to tokenize the input string by commas (,).
- It retrieves the first value from the stringstream to create the root node of the binary tree.
- It initializes a queue and pushes the root node into the queue.
- While the queue is not empty, it dequeues a node and processes its left and right children.
- It retrieves the next value from the stringstream and creates a left child if the value is not %.
- It retrieves the next value from the stringstream and creates a right child if the value is not %.
- If the value is %, it represents a NULL child, so the corresponding child node is set to NULL.
- The process continues until all nodes are processed, and the original binary tree is reconstructed.



---


### Code:

```
/**
 * 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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s = "";
        if(!root) return "";
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(node == NULL) s+="%,";
            else s+=(to_string(node->val) + ",");
            if(node != NULL){
                q.push(node->left);
                q.push(node->right);

            }
        }

        return s;

    }

    // Decodes your encoded data to tree.
    // Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if (data.size() == 0) return NULL;
    stringstream s(data);
    string str;
    getline(s, str, ','); // Get the first value from the stringstream

    TreeNode* root = new TreeNode(stoi(str));
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        // Process the left child
        getline(s, str, ','); // Get the next value from the stringstream
        if (str == "%") {
            node->left = NULL;
        } else {
            TreeNode* leftNode = new TreeNode(stoi(str));
            node->left = leftNode;
            q.push(leftNode);
        }
        // Process the right child
        getline(s, str, ','); // Get the next value from the stringstream
        if (str == "%") {
            node->right = NULL;
        } else {
            TreeNode* rightNode = new TreeNode(stoi(str));
            node->right = rightNode;
            q.push(rightNode);
        }
    }
    return root;
}

};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
```

### Complexity Analysis:
**Time:** O(N)
**Space:** O(N)

Thanks for reading.