Binary Tree Serialize and Deserialize

Description

Serializing a tree turns it into a flat string you can store or send. Deserializing rebuilds the exact same tree. A list of values alone loses the tree's shape. So the encoding also writes a marker for every missing child. With those markers, one traversal is enough to rebuild the tree, as long as the encoder and the decoder use the same one.

We'll go from simple to more technical:

1. The pattern: preorder with null markers, and one shared position in the string.
2. A second flavor: level order with null markers and a queue.
3. Where serialized trees live in production (syntax trees, query plans, caches).
4. The bugs that rebuild a different tree without any error.

The approach

Write the tree in preorder: the node, then its left subtree, then its right subtree. Write # wherever a child is missing. To decode, read the tokens in the same order. Each call reads one token. A number makes a node, and the call then builds its left and right subtrees from the tokens that follow. A # means "no node here", and the call returns.

Take this tree:

Its preorder encoding is 5,2,#,#,9,7,#,#,11,#,#. The decoder reads it like this:

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

TreeNode deserialize(Iterator<String> tokens) {
    String val = tokens.next();
    if (val.equals("#")) return null;
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserialize(tokens);    // consumes exactly this subtree's share of tokens...
    node.right = deserialize(tokens);   // ...before this call reads its own
    return node;
}

def serialize(node: TreeNode | None, out: list[str]) -> None:
    if node is None:
        out.append("#")
        return
    out.append(str(node.val))
    serialize(node.left, out)
    serialize(node.right, out)


def deserialize(tokens) -> TreeNode | None:    # tokens: ONE shared iterator, iter(data.split(","))
    val = next(tokens)
    if val == "#":
        return None
    node = TreeNode(int(val))
    node.left = deserialize(tokens)    # consumes exactly this subtree's share of tokens...
    node.right = deserialize(tokens)   # ...before this call reads its own
    return node

Every call shares one iterator, so there's one position in the string. The left call reads exactly the tokens of the left subtree and stops. The next unread token is then the start of the right subtree.

A second flavor: level order with a queue

Level order writes the tree row by row, with null for each missing child. The tree above becomes 5,2,9,null,null,7,11,null,null,null,null. The encoder is a breadth-first walk that writes null instead of skipping missing children. The decoder runs the same walk. It takes a node from the queue and reads the next two tokens as that node's children:

TreeNode deserialize(String data) {
    String[] tokens = data.split(",");
    if (data.isEmpty() || tokens[0].equals("null")) return null;
    TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
    Queue<TreeNode> queue = new ArrayDeque<>(List.of(root));
    for (int i = 1; !queue.isEmpty(); i += 2) {
        TreeNode node = queue.poll();
        if (!tokens[i].equals("null")) { node.left = new TreeNode(Integer.parseInt(tokens[i])); queue.offer(node.left); }
        if (!tokens[i + 1].equals("null")) { node.right = new TreeNode(Integer.parseInt(tokens[i + 1])); queue.offer(node.right); }
    }
    return root;
}

from collections import deque


def deserialize(data: str) -> TreeNode | None:
    tokens = data.split(",")
    if not data or tokens[0] == "null":
        return None
    root = TreeNode(int(tokens[0]))
    queue, i = deque([root]), 1
    while queue:
        node = queue.popleft()
        node.left = None if tokens[i] == "null" else TreeNode(int(tokens[i]))
        node.right = None if tokens[i + 1] == "null" else TreeNode(int(tokens[i + 1]))
        queue.extend(child for child in (node.left, node.right) if child)
        i += 2
    return root

Both sides walk the tree in the same order, so the decoder always knows which node the next two tokens belong to.

Where you'll see it

Every tree that's saved to disk, sent over a network or cached goes through this, from a compiler's syntax tree to a database's cached query plan. The order is your choice, as long as the writer and the reader agree on it.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. An encoding writes only the values, with no null markers. Why can't the decoder rebuild the tree?

2. A tree is written in level order, but the decoder reads the tokens as if they were preorder. What happens?

3. Why must the left and right calls in the preorder decoder share one iterator, instead of each getting its own?

Key takeaways

• Null markers record the tree's shape, so one traversal is enough to rebuild it.
• The encoder and decoder must use the same order. A mismatch builds a different tree with no error.
• Preorder with one shared iterator and level order with a queue are both fine choices.
• Test with a round trip: deserialize(serialize(tree)) must equal the original.