Serialize and Deserialize Binary Tree 🧠
LeetCode Link: Serialize and Deserialize Binary Tree
Difficulty: Hard
Problem Explanation 📝
Problem: LeetCode 297 - Serialize and Deserialize Binary Tree
Description: Design an algorithm to serialize and deserialize a binary tree. Serialize means to encode a tree structure into a string representation, and deserialize means to decode the string representation back into a binary tree structure. The encoded string should be as compact as possible.
Intuition: To serialize a binary tree, we can perform a pre-order traversal and encode the tree structure into a string. We use a special character to represent nullptr or empty nodes. During deserialization, we can use the encoded string to reconstruct the binary tree.
Approach:
- Serialization:
- Perform a pre-order traversal of the binary tree.
- When encountering a non-empty node, append its value to the serialized string, followed by a separator.
- When encountering a nullptr or empty node, append a special character (e.g., 'N') to represent it.
- Use a separator character (e.g., ',') to separate the values in the serialized string.
- Deserialization:
- Split the serialized string by the separator to obtain an array of values.
- Create a queue to hold the values from the array.
- Recursively build the binary tree using a helper function:
- If the queue is empty or the current value is the special character, return nullptr.
- Create a new node with the current value.
- Pop the queue to move to the next value.
- Set the left child of the current node by recursively calling the helper function.
- Set the right child of the current node by recursively calling the helper function.
- Return the current node.
- Call the helper function with the queue to build the binary tree.
- Return the root of the binary tree.
⌛ Time Complexity:
- Serialization: O(n), where n is the number of nodes in the binary tree. We perform a pre-order traversal to serialize the tree.
- Deserialization: O(n), where n is the number of nodes in the binary tree. We iterate through the serialized string to deserialize and reconstruct the tree.
💾 Space Complexity:
- Serialization: O(n), where n is the number of nodes in the binary tree. The serialized string requires space proportional to the number of nodes.
- Deserialization: O(n), where n is the number of nodes in the binary tree. We use a queue to store the values during deserialization.
Solutions 💡
Cpp 💻
/**
* 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:
string serialize(TreeNode *root) {
string serialized = "";
PreOrder(root, serialized);
return serialized;
}
TreeNode *deserialize(string data) {
queue<string> Q;
split(data, Q);
return MakeTree(Q);
}
private:
void PreOrder(TreeNode *root, string &str) {
if (!root) {
str.push_back('N');
str.push_back(',');
return;
}
str += to_string(root->val) + ",";
PreOrder(root->left, str);
PreOrder(root->right, str);
}
TreeNode *MakeTree(queue<string> &Q) {
string S = Q.front();
Q.pop();
if (S == "N") {
return nullptr;
}
// stoi -> string to integer
TreeNode *root = new TreeNode(stoi(S));
root->left = MakeTree(Q);
root->right = MakeTree(Q);
return root;
}
void split(const string &data, queue<string> &Q) {
size_t start = 0;
size_t pos = data.find(",");
while (pos != string::npos) {
Q.push(data.substr(start, pos - start));
start = pos + 1;
pos = data.find(",", start);
}
}
};
// class Codec {
// public:
// // Encodes a tree to a single string.
// string serialize(TreeNode* root) {
// string serialized = "";
// PreOrder(root, serialized);
// return serialized;
// }
// // Decodes your encoded data to tree.
// TreeNode* deserialize(string data) {
// queue<string> Q;
// string S;
// for(int i = 0; i < data.size(); i++) {
// // If it's a comma, push string into queue and reset string
// if(data[i] == ',') {
// Q.push(S);
// S = "";
// // Continuing so we go to next iteration without pushing comma
// continue;
// }
// // pushing back char to string if its not a comma
// S.push_back(data[i]);
// }
// // Making tree after decoding
// return MakeTree(Q);
// }
// private:
// // Function to make string using pre-order traversal
// void PreOrder(TreeNode* root, string &str) {
// // If root is null then insert N into string
// if(!root) {
// str.push_back('N');
// str.push_back(',');
// return;
// }
// // Converting int to string and appending
// // Another way of appending
// str += to_string(root->val) + ",";
// PreOrder(root->left, str);
// PreOrder(root->right, str);
// }
// TreeNode* MakeTree(queue<string> &Q) {
// string S = Q.front();
// Q.pop();
// if(S == "N")
// return NULL;
// // stoi -> string to integer
// TreeNode* root = new TreeNode(stoi(S));
// root->left = MakeTree(Q);
// root->right = MakeTree(Q);
// return root;
// }
// };
Python 🐍
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def preorder(node):
if not node:
return "None,"
return str(node.val) + "," + preorder(node.left) + preorder(node.right)
return preorder(root)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def build_tree(values):
if values[0] == "None":
values.pop(0)
return None
root = TreeNode(int(values.pop(0)))
root.left = build_tree(values)
root.right = build_tree(values)
return root
values = data.split(",")
return build_tree(values[:-1])
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))