Serialize and Deserialize Binary Tree

• Serialization converts a binary tree into a flat string that captures both structure and values.
• Null markers (such as #) record the absence of children, making a single preorder traversal fully reversible.
• Deserialization splits the string into tokens and consumes them in the same preorder order to rebuild the tree.
• Delimiter (such as ,) separates tokens unambiguously so multi-digit values are not merged.
• Time is O(n) in both directions; space is O(n) for the string and the recursion stack.

What is the Serialize and Deserialize Binary Tree problem?

Serialization converts a binary tree into a flat string that fully captures its structure and values. Deserialization reconstructs the exact same tree from that string. The core challenge is that a plain list of values loses the shape of the tree, so you must record the absence of children explicitly.

package com.bank.service;

import java.util.LinkedList;
import java.util.Queue;

public class HierarchySerializer {
    private static final String NULL_MARKER = "#";
    private static final String DELIMITER = ",";
}

Why do null markers make the encoding reversible?

Without null markers, the sequence [1, 2, 3] could represent many different tree shapes. With null markers, each branch termination is explicit, so the reader knows exactly where to stop building one branch and start the next. The sequence [1, 2, #, #, 3, #, #] unambiguously describes a tree with root 1, left child 2, and right child 3.

// Serialize: preorder traversal 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(NULL_MARKER).append(DELIMITER);
        return;
    }
    sb.append(node.val).append(DELIMITER);
    serializeHelper(node.left, sb);
    serializeHelper(node.right, sb);
}

Tree:       1
           / \
          2    3
             / \
            4    5

Serialized: "1,2,#,#,3,4,#,#,5,#,#,"

How does deserialization work?

You split the string into tokens and consume them in the same preorder order using a queue. Each token either builds a node and recursively builds its left and right children, or returns null if it is the null marker.

public TreeNode deserialize(String data) {
    if (data == null || data.isEmpty()) return null;
    Queue<String> queue = new LinkedList<>();
    for (String token : data.split(DELIMITER)) {
        queue.offer(token);
    }
    return deserializeHelper(queue);
}

private TreeNode deserializeHelper(Queue<String> queue) {
    String token = queue.poll();
    if (token == null || token.equals(NULL_MARKER)) return null;
    TreeNode node = new TreeNode(Integer.parseInt(token));
    node.left = deserializeHelper(queue);
    node.right = deserializeHelper(queue);
    return node;
}

Input:  "1,2,#,#,3,4,#,#,5,#,#,"
Tokens: [1, 2, #, #, 3, 4, #, #, 5, #, #]

Step 1: token=1 → create node(1)
  Step 2: token=2 → create node(2)
    Step 3: token=# → return null (left of 2)
    Step 4: token=# → return null (right of 2)
  Step 5: token=3 → create node(3)
    Step 6: token=4 → create node(4)
      Step 7: token=# → null
      Step 8: token=# → null
    Step 9: token=5 → create node(5)
      Step 10: token=# → null
      Step 11: token=# → null

Rebuilt tree matches original.

Why does the symmetry between serialize and deserialize matter?

Both operations process tokens in node-left-right order (preorder). Because the producer and consumer use the same traversal order, the stream of tokens reconstructs the tree exactly. This symmetry is the key insight: the null markers replace the structural information that a flat sequence would otherwise lose.

How is this different from level-order serialization?

Level-order (BFS) serialization writes nodes level by level and uses null markers for missing children. It is how LeetCode displays trees. Both approaches are valid and produce the same tree. Preorder is slightly easier to implement recursively; level-order is slightly easier to implement iteratively.

| Aspect | Preorder + Null Markers | Level-Order + Null Markers |
|--------|------------------------|---------------------------|
| Traversal | DFS (recursion) | BFS (queue) |
| Implementation | Simpler recursively | Simpler iteratively |
| Used by | Many interview solutions | LeetCode, many tools |
| Result | Same tree reconstructed | Same tree reconstructed |

What are edge cases?

• Null tree: serializes to #, and deserializes back to null.
• Single node: serializes to val,#,#,.
• Tree with negative values: the parser must handle the minus sign as part of the token.
• Very large values: the delimiter prevents multi-digit values from merging.

// Edge case: single node
// Tree: [5]
// Serialized: "5,#,#,"
// Deserialized back to a single node with value 5

// Edge case: negative values
// Tree: [-1, -2, -3]
// Serialized: "-1,-2,#,#,-3,#,#,"

What are common mistakes?

The first mistake is using a space or no delimiter at all, which merges multi-digit values. For example, 12 and 1,2 look the same without a delimiter. The second mistake is forgetting to handle the empty string case in deserialization. The third mistake is not using the same traversal order for both operations.

// WRONG: no delimiter between values
sb.append(node.val);  // "12" could be value 12 or values 1 and 2

// CORRECT: delimiter after every token
sb.append(node.val).append(",");  // "12," is unambiguously value 12

What about production serialization formats?

In production systems, you would typically use JSON, Protocol Buffers, or Avro rather than a bespoke string format. These formats handle edge cases like special characters, null values, and versioning. However, the preorder-with-null-markers scheme is the clearest to implement correctly in an interview and demonstrates understanding of the problem.

What about thread safety?

The serialization and deserialization operations are stateless if the preorder index or queue is local to the method call. If you use a shared mutable field (like a class-level index), concurrent calls will corrupt each other. Use local variables or pass state as parameters.

What should a senior engineer know?

At the National Bank of India, Rajesh used serialization to transmit and archive branch approval hierarchies. A branch serializes its hierarchy into a single text field that the central system persists, and later the central system deserializes it for audits. The explicit null sentinels and a clear delimiter guarantee the round trip is lossless. For large hierarchies, Rajesh used streaming serialization to avoid building the entire string in memory.