DSA
Serialize and Deserialize Binary Tree
Binary Trees problem — solution with code and analysis.
Practice Here
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.
Approach (BFS / Level-Order)#
- Intuition: A level-order (BFS) serialization records nodes row by row, including explicit "N" markers for null children. This is sufficient to reconstruct the tree because the positional relationship between a parent and its children is preserved by the order of the encoded values.
- Mechanics — Serialize: BFS enqueues both children of every non-null node (even if they are null, to record the "N" marker). Each node's value or "N" is appended with a comma delimiter. Trailing null markers at the very end are removed by popping the last character.
- Mechanics — Deserialize: The encoded string is split on commas into a token list. The root is built from token 0. A queue of created nodes is maintained; for each dequeued parent, the next two tokens are its left and right children (skipped if "N"). This mirrors the BFS order used during serialization.
- Trade-off: BFS serialization is easy to reason about and handles arbitrary tree shapes without ambiguity (unlike preorder serialization which requires careful index tracking). The explicit null markers do make the serialized string larger than some alternatives, but both operations remain O(n) time and space.
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:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(!root)
return "";
queue<TreeNode*> q;
q.push(root);
string str = "";
while(!q.empty())
{
TreeNode* node = q.front();
q.pop();
if(node){
str += to_string(node->val) + ',';
q.push(node->left);
q.push(node->right);
}
else
str += "N,";
}
str.pop_back();
cout<<str<<endl;
return str;
}
TreeNode* buildTree(vector<string> &nodeVals)
{
if(nodeVals.size()==1){
return new TreeNode(stoi(nodeVals[0]));
}
TreeNode* root = new TreeNode(stoi(nodeVals[0]));
queue<TreeNode*> q;
q.push(root);
int i =1;
while(!q.empty() && i < nodeVals.size())
{
TreeNode* curr = q.front();
q.pop();
if(i<nodeVals.size() && nodeVals[i] != "N")
{
curr->left = new TreeNode(stoi(nodeVals[i]));
q.push(curr->left);
}
i++;
if(i<nodeVals.size() && nodeVals[i] != "N")
{
curr->right = new TreeNode(stoi(nodeVals[i]));
q.push(curr->right);
}
i++;
}
return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.size()==0)
return NULL;
vector<string> nodeVals;
stringstream ss(data);
string nodeVal;
while(getline(ss, nodeVal, ',')){
nodeVals.push_back(nodeVal);
}
TreeNode* root = buildTree(nodeVals);
cout<<root->val;
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
Complexities#
| Function | Time Complexity | Space Complexity |
|---|---|---|
| serialize | O(n) | O(n) |
| deserialize | O(n) | O(n) |