Posted on Aug 3, 2023

DAY 61 - Serialize and Deserialize Binary Tree

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));