297 · Serialize and Deserialize Binary Tree

The null markers are the structure. Preorder with # for null is uniquely decodable; preorder without it is not, and inorder is not even with markers. Deserialization consumes the same stream in the same order — one shared cursor, never an index copy.

1 — The problem

Turn a tree into a string and the string back into the same tree. Any format is allowed, so the real question is: what is the minimum you must write down to make the tree recoverable?

LC 105 answered a related question — two traversals determine a tree — but here you control the encoding, so a single traversal will do, provided it records where the tree stops.

The reason preorder works and inorder does not: preorder puts the root first, so the decoder always knows what it is reading before it needs to know where the subtrees split. That is the same property that made preorder half of LC 105's answer.

2 — Write the stream, then read it back

Two phases in one visualizer. Phase 1 emits the string; phase 2 consumes it, token by token, and the tree reappears in the same order it was written.

The two methods are the same shape read in opposite directions: ser writes a token then descends; des reads a token then descends. Lines 4–5 and 12–13 are in the same order for the same reason — both walk preorder, so both must do left before right.

2.1 One shared cursor, never an index copy

The decoder's position in the stream is global to the whole decode, not per subtree. Every recursive call must see the consumption performed by its siblings and descendants, because they consumed their part of the stream and the cursor has to be past it.

This is the same distinction as LC 129 versus LC 257: value parameters give each frame its own copy, references share one. Here sharing is the requirement, not the hazard.

2.2 Details that bite

• Delimiters are mandatory. Without commas, a node valued 12 emits the same characters as 1 followed by 2. This is also what makes LC 572's string-matching solution require a guard character.
• Negative values mean you cannot use a bare - as a separator, and cannot assume tokens are single characters.
• split(",") drops trailing empty strings in Java, which is convenient here — the string ends with a comma and you do not want a phantom token.
• The marker must not be a legal value. # is safe; -1 is not, unless the constraints forbid it.
• Empty tree serializes to "#," and must round-trip back to null. Test it — it is the case that reveals whether the decoder handles a first token of #.

2.3 How many markers

A tree with n nodes has exactly n + 1 null slots — every node has two child slots, 2n in total, and n − 1 of them are occupied by non-root nodes. So the stream is always 2n + 1 tokens, regardless of shape. In the visualizer: 5 nodes, 6 markers, 11 tokens.

3 — Complexity and edge cases

• Time O(n) both ways; space O(n) for the string, O(h) for the recursion.
• Empty tree: round-trips through "#,".
• Single node: "1,#,#," — three tokens, matching 2n + 1.
• Skewed tree: O(n) recursion depth on both sides. At LeetCode's 10⁴-node limit this is fine; a level-order encoding with an explicit queue avoids the stack entirely.
• Common bug: passing the index by value, as above — the classic.
• Common bug: serializing with inorder because it "feels canonical". It is not decodable, and the failure only shows on asymmetric trees.

4 — Reference implementation

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

private void ser(TreeNode nd, StringBuilder sb) {
    if (nd == null) { sb.append("#,"); return; }   // the marker IS the structure
    sb.append(nd.val).append(',');
    ser(nd.left, sb);
    ser(nd.right, sb);
}

public TreeNode deserialize(String data) {
    Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(",")));
    return des(q);                          // ONE queue for the whole decode
}

private TreeNode des(Deque<String> q) {
    String t = q.poll();
    if (t.equals("#")) return null;
    TreeNode nd = new TreeNode(Integer.parseInt(t));
    nd.left  = des(q);                    // same order as ser — left, then right
    nd.right = des(q);
    return nd;
}

Related: LC 449 serializes a BST and needs no markers at all — the ordering carries the structure — and LC 652 uses this exact encoding as a hash-map key to find duplicate subtrees.