Serialize and Deserialize Tree
Serialize and deserialize a binary tree means converting the tree into a string (or array) and then reconstructing the original tree from that string. This is useful for saving trees to disk or sending over network.
We can use preorder traversal with null markers to preserve structure. Represent null nodes with a special marker, e.g., "#" .
Serialize (Preorder with null markers)
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("#,");
return;
}
sb.append(node.val).append(",");
serializeHelper(node.left, sb);
serializeHelper(node.right, sb);
}
Deserialize
Use a queue to process tokens from the serialized string.
public TreeNode deserialize(String data) {
Queue nodes = new LinkedList<>(Arrays.asList(data.split(",")));
return deserializeHelper(nodes);
}
private TreeNode deserializeHelper(Queue nodes) {
String val = nodes.poll();
if (val.equals("#")) return null;
TreeNode node = new TreeNode(Integer.parseInt(val));
node.left = deserializeHelper(nodes);
node.right = deserializeHelper(nodes);
return node;
}
Two Minute Drill
- Serialize: convert tree to string, often preorder with null markers.
- Deserialize: reconstruct tree from string using recursion/queue.
- Preserves tree structure exactly.
- Used in persistence and communication.
Need more clarification?
Drop us an email at career@quipoinfotech.com