Serialize and Deserialize Binary Tree (LC 297)

Pattern: Tree Traversal (Preorder + Null Markers)
Difficulty: Hard
Key Concept: A preorder string that records null for missing children uniquely defines the tree shape; deserialize consumes tokens left-to-right matching that preorder.

Problem Statement

Design an algorithm to serialize a binary tree to a string and deserialize the string back to the same tree structure.

Input / Output: LeetCode uses Codec with serialize(TreeNode root) → String and deserialize(String data) → TreeNode.

Constraints: Tree structure can be any binary tree; values fit in typical int string form.

Example

        1
       / \
      2   3
         / \
        4   5

One valid serialization (preorder with # for null):
1,2,#,#,3,4,#,#,5,#,#

---

1. Algorithm & Pseudocode

Brute force

1. Level order with explicit nulls: BFS; enqueue null placeholders; string can get many trailing nulls — works but bulky and harder to compress.
2. Two traversals without markers: store preorder of values only — ambiguous (cannot recover shape), so invalid as brute “correct” unless paired with another traversal and index logic (becomes optimal family).

Pseudocode (level-order brute)

serialize:
    q = [root]
    out = []
    while q not empty:
        n = q.pop()
        if n == null: out.add("null")
        else:
            out.add(str(n.val))
            q.add(n.left); q.add(n.right)  // may enqueue many nulls
    return join(out)

Optimal

1. Serialize: preorder DFS — append node.val or sentinel (e.g. "#" / "null") for null.
2. Deserialize: split string to queue/list of tokens; build() reads one token; if "#", return null; else create node, assign left = build(), right = build().

Pseudocode

function serialize(node):
    if node == null: return "#"
    return str(node.val) + "," + serialize(node.left) + "," + serialize(node.right)

tokens = split(data)

function build():
    t = next token
    if t == "#": return null
    node = new Node(parseInt(t))
    node.left = build()
    node.right = build()
    return node

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Preorder tells you “node first, then entire left subtree, then entire right” — perfect for recursive build.
• Why null markers: Without them, you only have values and cannot know where subtrees end (e.g. all left-skewed vs balanced with same multiset).
• Why not postorder only for naive deserialization: you can do it with a stack, but preorder + recursion is the standard teaching approach.
• Separators (commas) avoid ambiguity between multi-digit negatives and concatenated digits.

---

3. The Dry Run

Tree

    1
   / \
  2   3

Preorder serialization (comma-separated, # = null)

Tokens produced: 1, 2, #, #, 3, #, #

Recursive deserialize (build consumes from a queue):

Step	Token	Action
1	1	create node(1), recurse left
2	2	create node(2), recurse left
3	#	return null (2’s left)
4	#	return null (2’s right); finish 2
5	3	create node(3), left
6	#	null
7	#	null; done

ASCII rebuilt tree

    1
   / \
  2   3

---

4. Java Solution

Brute Force

Level-order with null sentinels (more tokens for wide sparse trees).

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

public class CodecBrute {
    // Serialize: O(n), extra nulls in queue-heavy representation
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringJoiner j = new StringJoiner(",");
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            if (n == null) {
                j.add("#");
            } else {
                j.add(String.valueOf(n.val));
                q.add(n.left);
                q.add(n.right);
            }
        }
        return j.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) return null;
        String[] tok = data.split(",");
        TreeNode root = nodeOf(tok[0]);
        Deque<TreeNode> parents = new ArrayDeque<>();
        parents.add(root);
        int i = 1;
        while (!parents.isEmpty() && i < tok.length) {
            TreeNode cur = parents.poll();
            if (!tok[i].equals("#")) {
                cur.left = nodeOf(tok[i]);
                parents.add(cur.left);
            }
            i++;
            if (i < tok.length && !tok[i].equals("#")) {
                cur.right = nodeOf(tok[i]);
                parents.add(cur.right);
            }
            i++;
        }
        return root;
    }

    private TreeNode nodeOf(String t) {
        return new TreeNode(Integer.parseInt(t));
    }
}

Note: The above BFS deserialize is simplified for LeetCode-style continuous BFS strings; preorder codec below is the canonical robust form.

Optimal

import java.util.*;

public class Codec {
    // Time: O(n) each way, Space: O(n) for tokens / recursion O(h)

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

    private void preorder(TreeNode n, StringBuilder sb) {
        if (n == null) {
            sb.append("#,");
            return;
        }
        sb.append(n.val).append(',');
        preorder(n.left, sb);
        preorder(n.right, sb);
    }

    public TreeNode deserialize(String data) {
        Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(",")));
        return build(q);
    }

    private TreeNode build(Deque<String> q) {
        String t = q.poll();
        if (t == null || t.isEmpty() || t.equals("#")) return null;
        TreeNode n = new TreeNode(Integer.parseInt(t));
        n.left = build(q);
        n.right = build(q);
        return n;
    }
}

---

5. The “Java vs. Others” Edge

• StringBuilder for serialization avoids O(n²) string copying from + in loops.
• StringJoiner or split(",") — watch empty trailing splits; LeetCode data usually has no trailing comma; if it does, filter empty tokens.
• Deque from ArrayDeque for token queue: O(1) poll from front.
• For very deep trees, recursion depth may require iterative deserialize with explicit stack (advanced).

---

6. Complexity Summary

Approach	Time	Space	Notes
BFS with nulls	O(n)	O(w) queue	String length can exceed minimal preorder on sparse wide trees
Preorder + #	O(n)	O(n) string + O(h) stack	Compact; standard interview answer