19. Serialize/Deserialize a Model-Config Tree

Problem

A training run's config is modeled as a binary override tree: each node has at most a primary-override child (the next config layered on top) and a secondary-override child (an alternate override branch, e.g. for an ablation). Persist a config tree to a single string that gets stored alongside a checkpoint's metadata, and reconstruct it exactly when the checkpoint is loaded later.

This is the classic LC297 preorder-with-null-markers approach: deserialize(serialize(root)) must reconstruct a tree structurally identical to the original root. Because trees aren't trivially comparable with ==, the test harness uses two helpers alongside serialize/deserialize: build_tree, which builds a TreeNode tree from a nested (val, left_spec, right_spec) tuple spec (or None), and trees_equal, which recursively compares two trees node-by-node.

Source: src/19_serialize_model_config_tree.py

class TreeNode:
    def __init__(self, val: str, left: "TreeNode | None" = None, right: "TreeNode | None" = None): ...

def serialize(root: "TreeNode | None") -> str: ...
def deserialize(data: str) -> "TreeNode | None": ...

>>> root = TreeNode("base", TreeNode("lr-sweep"), None)
>>> data = serialize(root)
>>> trees_equal(root, deserialize(data))
True

>>> serialize(None)
'#'

Step-by-Step Approach

1. Serialize: do a preorder traversal (visit node, then left, then right). At every None child, append a null marker ("#") to the output instead of recursing further — this is what lets deserialize later know exactly where each subtree ends without needing extra length/count metadata.
2. Collect all visited values (including the "#" markers) into a list, then join them with a delimiter (e.g. a comma) that can't appear inside a value, producing the final string.
3. Deserialize: split the string back into tokens by the same delimiter and wrap them in an iterator, so tokens can be consumed one at a time without index bookkeeping.
4. Write a recursive helper that pulls the next token: if it's the null marker, return None. Otherwise create a TreeNode with that value, then recursively build its left subtree (consuming more tokens), then its right subtree — in that order, mirroring the preorder serialization.
5. Because preorder is (root, left-subtree-tokens, right-subtree-tokens) with every subtree's boundary self-delimited by its own null markers, the recursive consumer always knows exactly how many tokens belong to the left subtree before it needs to start the right subtree — no separate boundary index is needed.

The key insight is that null markers make preorder self-delimiting: without them, you can't tell where a subtree ends just from its values, but with them, a single shared token stream is enough to unambiguously rebuild the exact tree shape in one recursive pass.

Reference solution

def serialize(root: "TreeNode | None") -> str:
    # preorder traversal with "#" null markers, O(n) time/space (LC297)
    vals: list[str] = []

    def _preorder(node: "TreeNode | None") -> None:
        if node is None:
            vals.append("#")
            return
        vals.append(node.val)
        _preorder(node.left)
        _preorder(node.right)

    _preorder(root)
    return ",".join(vals)


def deserialize(data: str) -> "TreeNode | None":
    # consume the preorder token stream, rebuilding null markers as None, O(n) time/space
    tokens = iter(data.split(","))

    def _build() -> "TreeNode | None":
        val = next(tokens)
        if val == "#":
            return None
        node = TreeNode(val)
        node.left = _build()
        node.right = _build()
        return node

    return _build()

Key Functions & Tricks

• "TreeNode | None" — forward-reference string type hint, avoids NameError before the class is fully defined.
• ",".join(vals) — concatenates a list into a delimited string.
• iter(data.split(",")) — tokenizes on ",", wraps in an iterator for one-at-a-time consumption.
• next(tokens) — advances and permanently consumes the iterator's next value.
• Nested closures — _preorder/_build share vals/tokens without passing them as explicit parameters.
• Recursion order mirrors traversal order — root, then left, then right, matching serialization exactly.

How to Recognize This Pattern