Serialize and Deserialize Binary Tree — Preorder With Null Sentinels

This is the classic systems-flavored tree problem. You are not asked to compute anything; you are asked to design an encoding that round-trips perfectly. Most candidates get the serialize right and stumble on the deserialize because they forget the one invariant that makes both halves trivial: preorder plus explicit nulls is enough.

The Problem

Implement two functions: serialize(root) returns a string representation of a binary tree, and deserialize(data) reconstructs the original tree from that string. The encoding format is your call. Trees may contain arbitrary integer values and arbitrary shapes, including empty.

Intuition

Preorder alone is ambiguous because you cannot tell where missing children are. The fix is a null sentinel. Every recursive call emits either a value or the sentinel before recursing into children. On the decode side, walk the tokens in order and consume them with the same recursion shape. The trick that makes deserialization clean is to pass the same iterator object into every recursive call — it advances the cursor automatically with no index bookkeeping.

Explanation with Example

Take the tree:

    1
   / \
  2   3
     / \
    4   5

Serialization runs preorder: 1, 2, #, #, 3, 4, #, #, 5, #, #. Joined: "1,2,#,#,3,4,#,#,5,#,#".

Deserialization:

• Read 1. Build node. Recurse left.
• Read 2. Build node. Recurse left.
• Read #. Return None. Recurse right.
• Read #. Return None. Node 2 is done.
• Back at node 1, recurse right. Read 3. Build. Recurse left.
• Read 4. Build. Two # tokens make 4 a leaf.
• Back at node 3, recurse right. Read 5. Two # tokens make 5 a leaf.

The tree is reconstructed exactly.

tree:                preorder tokens (#=null):
     1              1, 2, #, #, 3, 4, #, #, 5, #, #
    / \
   2   3            visit order: root, left subtree, right subtree
      / \
     4   5          encode: emit val; recurse L; recurse R
                            for None, emit "#"

decode walk (iterator advances one token per call):
build() reads 1  -> node(1).left = build(), .right = build()
  build() reads 2 -> node(2).left=build()=#  .right=build()=#
  build() reads 3 -> ...

Code

class Codec:
    def serialize(self, root):
        out = []
        def dfs(node):
            if not node:
                out.append("#")
                return
            out.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ",".join(out)

    def deserialize(self, data):
        tokens = iter(data.split(","))
        def build():
            val = next(tokens)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        return build()

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

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

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

    private TreeNode build(Deque<String> tokens) {
        String val = tokens.pollFirst();
        if (val.equals("#")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = build(tokens);
        node.right = build(tokens);
        return node;
    }
}

class Codec {
public:
    string serialize(TreeNode* root) {
        string out;
        dfs(root, out);
        return out;
    }

    void dfs(TreeNode* node, string& out) {
        if (!node) { out += "#,"; return; }
        out += to_string(node->val) + ",";
        dfs(node->left, out);
        dfs(node->right, out);
    }

    TreeNode* deserialize(string data) {
        size_t pos = 0;
        return build(data, pos);
    }

    TreeNode* build(string& data, size_t& pos) {
        size_t next = data.find(',', pos);
        string val = data.substr(pos, next - pos);
        pos = next + 1;
        if (val == "#") return nullptr;
        TreeNode* node = new TreeNode(stoi(val));
        node->left = build(data, pos);
        node->right = build(data, pos);
        return node;
    }
};

Edge Cases

• Empty tree — serializes to "#", deserializes to None.
• A single node — "7,#,#".
• Negative values — make sure your tokenizer treats - as part of the number, not a delimiter.
• Very large trees — Python recursion limits matter. Bump sys.setrecursionlimit or write the iterative version with an explicit stack.
• Duplicates — totally fine. The encoding does not care.

Complexity Analysis

Both serialize and deserialize are O(n) time, where n is the number of nodes (including the implicit null leaves we emit). Space is O(n) for the output string and O(h) for recursion, where h is the tree height. Level-order encodings have the same asymptotics but pay more in string size for sparse trees because they fill every position up to the deepest level.

For a refresher on why “O(n) time, O(h) space” is the standard tree budget, see Big-O Notation Explained.

How to Explain It in an Interview

Lead with the invariant: “Preorder alone is ambiguous — you need to know where missing children are. The fix is a null sentinel.” Sketch the serializer. For the deserializer, draw attention to the shared iterator: it is the trick that turns a fiddly index problem into a clean recursion.

If asked about level-order, acknowledge it works but point out two costs: the BFS code is longer, and sparse trees waste bytes. If asked about JSON or other structured formats, note that they are fine but most interviewers want a flat tokenized format because it shows you understand the algorithm.

Related Problems

• Serialize and Deserialize BST (lets you skip the nulls)
• Construct Binary Tree from Preorder and Inorder
• Serialize and Deserialize N-ary Tree
• Find Duplicate Subtrees (uses serialization as a hash key)

The N-ary case is a fun extension — instead of two recursive calls per node, you emit the child count first.

Wrap up

This problem rewards a small, sharp insight: preorder traversal plus a null token is a self-describing format. Internalize the iterator-driven decoder — it generalizes to almost every recursive-parsing problem you will see, from expression trees to nested JSON. The same recursive shape you use in tree traversals shows up here doing double duty.