Serialize and Deserialize a Binary Tree
Serializing and Deserializing Binary Tree – Medium Level Problem
Create an algorithm to convert a binary tree into a string (serialization) and then reconstruct the same binary tree from that string (deserialization).
Serialization means converting a binary tree into a format that can be saved or sent to another system. Deserialization means converting that saved format back into the original binary tree.
Goal is to ensure that the binary tree can be serialized into a string and later deserialized back to its original structure without any loss of information. There are no specific rules for how you should implement this; the approach is up to you.
Example 1
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2
Input: root = []
Output: []
Output: []
Constraints:
- 0 <= The number of nodes in the tree <= 1000.
- -1000 <= Node.val <= 1000
Serialize and Deserialize a Binary Tree
Recommendation for Time and Space Complexity – Try to solve the problem with O(n) time and O(n) space, where n is the total number of nodes in the binary tree.
Hints for solving problems
Hint 1 :
One simple way to serialize a tree is to traverse it and store the node values in a string, separated by a delimiter (e.g., “,”). However, this can create issues when dealing with null nodes because it becomes unclear how to reconstruct the tree accurately. Can you think of a way to include null nodes explicitly during serialization?
Hint 2 :
By using a placeholder like “N” for null nodes during serialization, you can preserve the tree’s structure. This placeholder helps identify missing children, making it easier to reconstruct the tree during deserialization.
Hint 3 :
You can use Depth First Search (DFS) for both serialization and deserialization:
- Serialization: Traverse the tree with DFS, adding node values to the string and inserting “N” wherever there is a null node.
- Deserialization: Process the serialized string step-by-step using an index. For valid node values, create new tree nodes. When encountering “N”, treat it as a null node and return from that path. This approach ensures accurate reconstruction of the tree.
There are mainly 2 approach to solve this problem-
- Depth First Search Method
- Breadth First Search Method
1. Depth First Search Method
In the DFS approach, we use preorder traversal to serialize the binary tree by storing node values in the sequence they are visited. During deserialization, the stored data is used recursively to reconstruct the tree by maintaining the traversal order.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector<string> res;
dfsSerialize(root, res);
return join(res, ",");
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<string> vals = split(data, ',');
int i = 0;
return dfsDeserialize(vals, i);
}
private:
void dfsSerialize(TreeNode* node, vector& res) {
if (!node) {
res.push_back("N");
return;
}
res.push_back(to_string(node->val));
dfsSerialize(node->left, res);
dfsSerialize(node->right, res);
}
TreeNode* dfsDeserialize(vector& vals, int& i) {
if (vals[i] == "N") {
i++;
return NULL;
}
TreeNode* node = new TreeNode(stoi(vals[i]));
i++;
node->left = dfsDeserialize(vals, i);
node->right = dfsDeserialize(vals, i);
return node;
}
vector split(const string &s, char delim) {
vector<string> elems;
stringstream ss(s);
string item;
while (getline(ss, item, delim)) {
elems.push_back(item);
}
return elems;
}
string join(const vector &v, const string &delim) {
ostringstream s;
for (const auto &i : v) {
if (&i != &v[0])
s << delim;
s << i;
}
return s.str();
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
List<String> res = new ArrayList<>();
dfsSerialize(root, res);
return String.join(",", res);
}
private void dfsSerialize(TreeNode node, List res) {
if (node == null) {
res.add("N");
return;
}
res.add(String.valueOf(node.val));
dfsSerialize(node.left, res);
dfsSerialize(node.right, res);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] vals = data.split(",");
int[] i = {0};
return dfsDeserialize(vals, i);
}
private TreeNode dfsDeserialize(String[] vals, int[] i) {
if (vals[i[0]].equals("N")) {
i[0]++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(vals[i[0]]));
i[0]++;
node.left = dfsDeserialize(vals, i);
node.right = dfsDeserialize(vals, i);
return node;
}
}
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Codec:
# Encodes a tree to a single string.
def serialize(self, root: Optional[TreeNode]) -> str:
res = []
def dfs(node):
if not node:
res.append("N")
return
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(res)
# Decodes your encoded data to tree.
def deserialize(self, data: str) -> Optional[TreeNode]:
vals = data.split(",")
self.i = 0
def dfs():
if vals[self.i] == "N":
self.i += 1
return None
node = TreeNode(int(vals[self.i]))
self.i += 1
node.left = dfs()
node.right = dfs()
return node
return dfs()
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Codec {
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
serialize(root) {
const res = [];
this.dfsSerialize(root, res);
return res.join(',');
}
dfsSerialize(node, res) {
if (node === null) {
res.push('N');
return;
}
res.push(node.val.toString());
this.dfsSerialize(node.left, res);
this.dfsSerialize(node.right, res);
}
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
deserialize(data) {
const vals = data.split(',');
const i = { val: 0 };
return this.dfsDeserialize(vals, i);
}
dfsDeserialize(vals, i) {
if (vals[i.val] === 'N') {
i.val++;
return null;
}
const node = new TreeNode(parseInt(vals[i.val]));
i.val++;
node.left = this.dfsDeserialize(vals, i);
node.right = this.dfsDeserialize(vals, i);
return node;
}
}
2. Breadth First Search Method
In the BFS approach, the binary tree is serialized level by level using a queue to store node values. During deserialization, the data is processed sequentially to rebuild the tree by connecting child nodes level-wise.
- Time complexity: O(n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root) return "N";
string res;
queue<TreeNode*> queue;
queue.push(root);
while (!queue.empty()) {
TreeNode* node = queue.front();
queue.pop();
if (!node) {
res += "N,";
} else {
res += to_string(node->val) + ",";
queue.push(node->left);
queue.push(node->right);
}
}
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
stringstream ss(data);
string val;
getline(ss, val, ',');
if (val == "N") return nullptr;
TreeNode* root = new TreeNode(stoi(val));
queue<TreeNode*> queue;
queue.push(root);
while (getline(ss, val, ',')) {
TreeNode* node = queue.front();
queue.pop();
if (val != "N") {
node->left = new TreeNode(stoi(val));
queue.push(node->left);
}
getline(ss, val, ',');
if (val != "N") {
node->right = new TreeNode(stoi(val));
queue.push(node->right);
}
}
return root;
}
};
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "N";
StringBuilder res = new StringBuilder();
Queu<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
res.append("N,");
} else {
res.append(node.val).append(",");
queue.add(node.left);
queue.add(node.right);
}
}
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] vals = data.split(",");
if (vals[0].equals("N")) return null;
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int index = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (!vals[index].equals("N")) {
node.left = new TreeNode(Integer.parseInt(vals[index]));
queue.add(node.left);
}
index++;
if (!vals[index].equals("N")) {
node.right = new TreeNode(Integer.parseInt(vals[index]));
queue.add(node.right);
}
index++;
}
return root;
}
}
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Codec:
# Encodes a tree to a single string.
def serialize(self, root: Optional[TreeNode]) -> str:
if not root:
return "N"
res = []
queue = deque([root])
while queue:
node = queue.popleft()
if not node:
res.append("N")
else:
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
return ",".join(res)
# Decodes your encoded data to tree.
def deserialize(self, data: str) -> Optional[TreeNode]:
vals = data.split(",")
if vals[0] == "N":
return None
root = TreeNode(int(vals[0]))
queue = deque([root])
index = 1
while queue:
node = queue.popleft()
if vals[index] != "N":
node.left = TreeNode(int(vals[index]))
queue.append(node.left)
index += 1
if vals[index] != "N":
node.right = TreeNode(int(vals[index]))
queue.append(node.right)
index += 1
return root
JavaScript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Codec {
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
serialize(root) {
if (!root) return "N";
const res = [];
const queue = new Queue();
queue.push(root);
while (!queue.isEmpty()) {
const node = queue.pop();
if (!node) {
res.push("N");
} else {
res.push(node.val);
queue.push(node.left);
queue.push(node.right);
}
}
return res.join(",");
}
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
deserialize(data) {
const vals = data.split(",");
if (vals[0] === "N") return null;
const root = new TreeNode(parseInt(vals[0]));
const queue = new Queue([root]);
let index = 1;
while (!queue.isEmpty()) {
const node = queue.pop();
if (vals[index] !== "N") {
node.left = new TreeNode(parseInt(vals[index]));
queue.push(node.left);
}
index++;
if (vals[index] !== "N") {
node.right = new TreeNode(parseInt(vals[index]));
queue.push(node.right);
}
index++;
}
return root;
}
}
