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
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:
- 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.
Top comments (0)