209. Serialize and Deserialize Binary Tree

Pre-order traversal (root, left, right) does not uniquely determine a binary tree on its own — [1, 2] could mean "root 1 with left child 2" or "root 1 with right child 2". Adding explicit null markers fixes this: the sequence becomes a complete recipe the deserializer can follow blindly.

Why null markers matter

Without nulls:

Tree A:    1            Tree B:   1
          /                        \
         2                          2

Both produce pre-order [1, 2]. The deserializer can't tell them apart.

With nulls (# for missing child):

Tree A: 1, 2, #, #, #
Tree B: 1, #, 2, #, #

Now the sequence is unambiguous — at every step you know whether the next slot is a real node or a null.

Serialize

A pre-order DFS:

1. If the current node is None, emit #.
2. Otherwise, emit node.val, then recurse left, then recurse right.
3. Join everything into a comma-separated string.

Deserialize

Use the same pre-order recipe in reverse, consuming tokens one by one with an iterator:

1. Take the next token.
2. If it's #, return None.
3. Otherwise, create a node with that value, recurse to build its left subtree, recurse to build its right subtree, and return the node.

The order of recursion mirrors how serialize emitted children, so the iterator's position always lines up.

Walk-through

Tree:

    1
   / \
  2   3
     / \
    4   5

Serialize: dfs(1) emits 1. dfs(2) emits 2, then dfs(None) × 2 emits #, #. Back at root, dfs(3) emits 3. dfs(4) emits 4, #, #. dfs(5) emits 5, #, #.

Result: "1,2,#,#,3,4,#,#,5,#,#".

Deserialize that string:

build()  ← reads "1", creates Node(1)
  build() for left  ← reads "2", creates Node(2)
    build() for left  ← reads "#", returns None
    build() for right ← reads "#", returns None
    return Node(2)
  build() for right  ← reads "3", creates Node(3)
    build() for left  ← reads "4", creates Node(4)
      build() for left  ← reads "#", returns None
      build() for right ← reads "#", returns None
      return Node(4)
    build() for right  ← reads "5", creates Node(5)
      build() for left  ← reads "#", returns None
      build() for right ← reads "#", returns None
      return Node(5)
    return Node(3)
  return Node(1)

Identical tree reconstructed. ✓

Edge cases

• Empty tree (root is None): serialize emits just #. Deserialize reads # and returns None. Round-trip works.
• Single node: serialize emits val,#,#. Deserialize creates the node and reads two nulls.
• Negative values: comma-separated with int() parsing handles them fine.

Complexity

• Time: O(n) for both serialize and deserialize.
• Space: O(n) for the output string and the recursion stack.

import java.util.*;

class Codec {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public String serialize(TreeNode root) {
        List<String> out = new ArrayList<>();
        dfsSerialize(root, out);
        return String.join(",", out);
    }

    private void dfsSerialize(TreeNode node, List<String> out) {
        if (node == null) {
            out.add("#");
            return;
        }
        out.add(String.valueOf(node.val));
        dfsSerialize(node.left, out);
        dfsSerialize(node.right, out);
    }

    public TreeNode deserialize(String data) {
        Iterator<String> it = Arrays.asList(data.split(",")).iterator();
        return dfsBuild(it);
    }

    private TreeNode dfsBuild(Iterator<String> it) {
        String v = it.next();
        if (v.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(v));
        node.left = dfsBuild(it);
        node.right = dfsBuild(it);
        return node;
    }
}