5.32 Binary Tree Serialization

5.32.1 Problem Metadata

5.32.2 Description

Design an algorithm to serialize and deserialize a binary tree. Serialization is converting a tree to a string, and deserialization is reconstructing the tree from that string.

5.32.3 Examples

Input: root = [1,2,3,null,null,4,5]
Serialized: "1,2,#,#,3,4,#,#,5,#,#"
Output after deserialize: [1,2,3,null,null,4,5]

5.32.4 Constraints

  • The number of nodes is in the range [0, 10^4]
  • -1000 <= Node.val <= 1000

5.32.5 Solution - Preorder with Null Markers

5.32.5.1 Walkthrough

This solution uses preorder traversal with null markers to achieve a complete and reversible serialization.

Core Strategy:

  1. Serialize: Perform preorder DFS, recording each node’s value. Use a special marker (#) for null nodes.
  2. Deserialize: Read values in order, recursively building the tree. When # is encountered, return null.

Why Preorder Works: Preorder visits root first, then left subtree, then right subtree. By marking null children, we have enough information to uniquely reconstruct the tree.

Example: Tree [1,2,3,null,null,4,5]:

      1
     / \
    2   3
       / \
      4   5

Serialize (preorder): 1 → 2 → # → # → 3 → 4 → # → # → 5 → # → #
Result: "1,2,#,#,3,4,#,#,5,#,#"

5.32.5.2 Analysis

  • Time Complexity: O(n) - Each node visited once in both operations
  • Space Complexity: O(n) - String storage for serialization, O(h) recursion stack

5.32.5.3 Implementation Steps

  1. Serialize: DFS preorder, append value or # for null, separate with delimiter.
  2. Deserialize: Split string into queue, recursively build tree by polling values.

5.32.5.4 Code - Java

private static final String SEP = ",";
private static final String NULL = "#";

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

private void serialize(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append(NULL).append(SEP);
        return;
    }
    sb.append(node.val).append(SEP);
    serialize(node.left, sb);
    serialize(node.right, sb);
}

public TreeNode deserialize(String data) {
    Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(SEP)));
    return deserialize(queue);
}

private TreeNode deserialize(Queue<String> queue) {
    String val = queue.poll();
    if (val.equals(NULL)) {
        return null;
    }
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserialize(queue);
    node.right = deserialize(queue);
    return node;
}