Approach 1: Pre-order Traversal
Perform a pre-order traversal of the tree to serialize it and instead of NULL nodes, store a placeholder like “#”. It is important to store null nodes because they are used in deserializing the tree. Just like in a pre-order recursive traversal of the tree, you return when you encounter a NULL node, we’ll return from the recursive deserializing function when we encounter a “#”.
class Codec {
private:
int i = 0; // used by deserialize function
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL)
return "#";
return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data[i] == '#') {
i+=2;
return NULL;
}
int idx = data.find(",", i);
TreeNode *root = new TreeNode(stoi(data.substr(i, idx-i)));
i=idx+1;
root->left = deserialize(data);
root->right = deserialize(data);
return root;
}
};
Time complexity: O(n) of serialize if we consider concatenating strings as O(1) operation else probably O(n^2). O(n) of deserialize.
Space complexity: O(n)
Approach 2: BFS
We can also perform BFS to serialize and deserialize a tree. In this approach, we store “n” for NULL nodes and we have to keep track of all the null nodes at each level. For example:
1
/ \
2 3
/ \
4 5
This tree serializes to "1 2 3 n n 4 5 n n n n "
Java solution:
public class Codec {
public String serialize(TreeNode root) {
if (root == null) return "";
Queue<TreeNode> q = new LinkedList<>();
StringBuilder res = new StringBuilder();
q.add(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) {
res.append("n ");
continue;
}
res.append(node.val + " ");
q.add(node.left);
q.add(node.right);
}
return res.toString();
}
public TreeNode deserialize(String data) {
if (data == "") return null;
Queue<TreeNode> q = new LinkedList<>();
String[] values = data.split(" ");
TreeNode root = new TreeNode(Integer.parseInt(values[0]));
q.add(root);
for (int i = 1; i < values.length; i++) {
TreeNode parent = q.poll();
if (!values[i].equals("n")) {
TreeNode left = new TreeNode(Integer.parseInt(values[i]));
parent.left = left;
q.add(left);
}
if (!values[++i].equals("n")) {
TreeNode right = new TreeNode(Integer.parseInt(values[i]));
parent.right = right;
q.add(right);
}
}
return root;
}
}
Time complexity: Both serialize and deserialize take O(N) time
Space complexity: O(width) where width is the max width of the tree