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]
Example 2:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 104]
. -1000 <= Node.val <= 1000
Serialize and Deserialize Binary Tree Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root)
return "";
string s;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node) {
s += to_string(node->val) + " ";
q.push(node->left);
q.push(node->right);
} else {
s += "n ";
}
}
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.empty())
return nullptr;
istringstream iss(data);
string word;
iss >> word;
TreeNode* root = new TreeNode(stoi(word));
queue<TreeNode*> q{{root}};
while (iss >> word) {
TreeNode* node = q.front();
q.pop();
if (word != "n") {
node->left = new TreeNode(stoi(word));
q.push(node->left);
}
iss >> word;
if (word != "n") {
node->right = new TreeNode(stoi(word));
q.push(node->right);
}
}
return root;
}
};
Java
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null)
return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root));
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) {
sb.append("n ");
} else {
sb.append(node.val).append(" ");
q.offer(node.left);
q.offer(node.right);
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals(""))
return null;
final String[] vals = data.split(" ");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root));
for (int i = 1; i < vals.length; i += 2) {
TreeNode node = q.poll();
if (!vals[i].equals("n")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
q.offer(node.left);
}
if (!vals[i + 1].equals("n")) {
node.right = new TreeNode(Integer.parseInt(vals[i + 1]));
q.offer(node.right);
}
}
return root;
}
}
Python
class Codec:
def serialize(self, root: 'TreeNode') -> str:
"""Encodes a tree to a single string."""
if not root:
return ''
s = ''
q = deque([root])
while q:
node = q.popleft()
if node:
s += str(node.val) + ' '
q.append(node.left)
q.append(node.right)
else:
s += 'n '
return s
def deserialize(self, data: str) -> 'TreeNode':
"""Decodes your encoded data to tree."""
if not data:
return None
vals = data.split()
root = TreeNode(vals[0])
q = deque([root])
for i in range(1, len(vals), 2):
node = q.popleft()
if vals[i] != 'n':
node.left = TreeNode(vals[i])
q.append(node.left)
if vals[i + 1] != 'n':
node.right = TreeNode(vals[i + 1])
q.append(node.right)
return root
Watch Tutorial
Checkout more Solutions here