Q18: How do you Serialize and Deserialize a Binary Tree?

Serialization: Convert tree to string using Pre-Order DFS traversal, appending "#" or "null" for null pointers, separated by commas.
Deserialization: Split string by comma into a Queue<String>. Reconstruct tree recursively by polling values, creating nodes, and assigning left/right child subtrees.

Binary Tree Serialization and Deserialization

import java.util.*;

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }
    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) { sb.append("#,"); return; }
        sb.append(node.val).append(",");
        buildString(node.left, sb);
        buildString(node.right, sb);
    }
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return buildTree(nodes);
    }
    private TreeNode buildTree(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
        return node;
    }
}

💡 Serializes nodes with null boundary markers and reconstructs tree nodes in pre-order.

Key Takeaways

Pre-order DFS traversal with null markers enables unambiguous tree reconstruction.
Queue-based deserialization matches pre-order node creation.

Knowledge Check

Why are explicit null markers (e.g. "#") necessary when serializing a binary tree using pre-order traversal?

Q18: How do you Serialize and Deserialize a Binary Tree?

STAY UPDATED WITH BYTES!