Problem
Design an algorithm to serialize and deserialize a binary tree. Serialization converts the tree into a string so that it can be stored or transmitted. Deserialization reconstructs the original binary tree from that string.Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [1,2,3,null,null,4,5]
1
/ \
2 3
/ \
4 5
Output
Serialized: "1,2,#,#,3,4,#,#,5,#,#"
Deserialized:
1
/ \
2 3
/ \
4 5
Solution
This solution uses Depth-First Search (DFS) with preorder traversal. Each node is stored before recursively processing its left and right children.For a
null node, a special marker such as # is stored. These markers are important because they preserve the exact structure of the tree, including missing children.
During deserialization, the values are processed in the same preorder sequence. A
# represents a null node. Otherwise, a new node is created, followed by recursively constructing its left and right children.
public class Codec {
private static final String NULL = "#";
private static final String SEPARATOR = ",";
public String serialize(TreeNode root) {
StringBuilder result = new StringBuilder();
serialize(root, result);
return result.toString();
}
private void serialize(TreeNode node, StringBuilder result) {
if (node == null) {
result.append(NULL).append(SEPARATOR);
return;
}
// Store the current node first.
result.append(node.val).append(SEPARATOR);
serialize(node.left, result);
serialize(node.right, result);
}
public TreeNode deserialize(String data) {
Queue<String> values = new LinkedList<>(
Arrays.asList(data.split(SEPARATOR))
);
return deserialize(values);
}
private TreeNode deserialize(Queue<String> values) {
String value = values.poll();
// Null marker represents an empty child.
if (NULL.equals(value)) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(value));
// Reconstruct left and right subtrees.
node.left = deserialize(values);
node.right = deserialize(values);
return node;
}
}
Complexity
Each node and its correspondingnull markers are processed once during serialization and deserialization, resulting in a time complexity of O(n).
The serialized data, queue, and recursive call stack require
O(n) space in the worst case.