297. Serialize and Deserialize Binary Tree

Most tree problems hand you a tree and ask a question about it. This one asks you to flatten a tree into a string and rebuild it byte-for-byte — the encoding is the problem. It’s the clearest test in the binary tree pattern of whether you really understand what a preorder traversal preserves.

The problem

Write two functions: one turns a binary tree into a string, the other turns that string back into the identical tree — same shape, same values. The format is entirely your choice; it just has to round-trip. (Full statement on LeetCode.)

The catch that trips people up: a tree is not a list. If you only write down the node values you visit, [1, 2] could mean “2 is the left child of 1” or “2 is the right child of 1” — you’ve lost the shape.

Intuition: null markers are what restore the shape

A plain preorder list of values is ambiguous because it never records where a subtree ends. Fix that by writing down the empty children too. Do a preorder walk — root, then left subtree, then right subtree — and every time you hit a missing child, emit a sentinel like N instead of skipping it:

$\text{encode}(node) = \text{val},\ \text{encode}(left),\ \text{encode}(right)$

with encode(null) = N. Now the string is unambiguous. When you read it back in the same preorder order, the first token is always the current node, and the two subtrees that follow are delimited precisely by their own null markers — there’s no guessing where the left subtree stops and the right begins, because the nulls mark every boundary.

That symmetry is the whole trick: the deserializer consumes tokens in exactly the order the serializer produced them. One shared traversal order, read forward, rebuilds the tree.

Solution

Serialize with a recursive preorder that appends N for nulls. Deserialize by pulling tokens off the front of a queue in the same order — each call reads one node, then recursively fills its left and right.

import java.util.*;

public class Codec {

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

    // Preorder: value, then left subtree, then right subtree.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        encode(root, sb);
        return sb.toString();
    }

    private void encode(TreeNode node, StringBuilder sb) {
        if (node == null) {          // record the empty child explicitly
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP);
        encode(node.left, sb);       // same order the decoder will read
        encode(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        // Queue lets us pop tokens front-to-back in preorder.
        Queue<String> tokens = new LinkedList<>(Arrays.asList(data.split(SEP)));
        return decode(tokens);
    }

    private TreeNode decode(Queue<String> tokens) {
        String token = tokens.poll();
        if (NULL.equals(token)) {    // a null marker closes this branch
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(token));
        node.left = decode(tokens);  // consume left subtree first...
        node.right = decode(tokens); // ...then right, matching encode()
        return node;
    }
}

Two things make this safe. A letter sentinel like N can never collide with a value token, even negative ones like -1000, so parsing stays unambiguous. And the queue guarantees the decoder reads left-then-right in lockstep with how the encoder wrote them.

Complexity

	Time	Space
Serialize	$O(n)$	$O(n)$
Deserialize	$O(n)$	$O(n)$

Each node is visited once in both directions, so both are linear in the node count $n$. The space is the serialized string plus the recursion stack, which is $O(n)$ in the worst case of a fully skewed tree.

In an interview

Say the ambiguity out loud before you write anything: “values alone lose the structure, so I’ll record nulls explicitly.” That one sentence shows you know why the naive approach fails, which is what separates a clean answer from a lucky one. Then pick preorder — it’s the easiest to reverse because the root comes first, so the decoder always knows which node it’s building before it recurses.

Watch two edge cases the interviewer will poke at: the empty tree (a null root must serialize and come back as null, not crash), and negative values (why a letter sentinel beats reusing -1 as the null marker). If they push on very deep skewed trees, mention that recursion could hit the stack limit and an explicit stack or BFS layout would sidestep it.

This is really Construct Binary Tree from Preorder and Inorder Traversal turned inside out — there you rebuild from two traversals, here the null markers let a single preorder do the job alone. If you’d rather encode level by level, the level-order traversal gives you the BFS layout LeetCode itself uses. Both live in the binary tree pattern hub.

References

• LeetCode 297 — Serialize and Deserialize Binary Tree