43. Serialize Pipeline Config Tree

Problem

A pipeline's stage-fallback config is modeled as a binary tree: each stage has at most a primary child (the next stage to try) and a fallback child (the stage to fall back to if the primary path fails). Persist a config tree to a single string, and reconstruct it from that string — e.g. to store and diff config versions.

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 for structural and value equality.

Source: src/43_serialize_pipeline_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("primary", TreeNode("fallback"), None)
>>> data = serialize(root)
>>> trees_equal(root, deserialize(data))
True

>>> serialize(None)
'#'
>>> deserialize('#') is None
True

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

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


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

    # closure over vals, no explicit param threading
    def _preorder(node: "TreeNode | None") -> None:
        if node is None:
            vals.append("#")
            return
        vals.append(node.val)
        # recursion order mirrors traversal: root, left, right
        _preorder(node.left)
        _preorder(node.right)

    _preorder(root)
    # str.join, faster than repeated += concatenation
    return ",".join(vals)


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

    def _build() -> "TreeNode | None":
        # advances and permanently consumes the next token
        val = next(tokens)
        if val == "#":
            return None
        node = TreeNode(val)
        # same order as _preorder wrote tokens, so no boundary tracking needed
        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 consumes the iterator's next value.
• Nested closures — _preorder/_build share vals/ tokens without passing them as params.
• Recursion order mirrors traversal order — root, then left, then right, matching serialization.

How to Recognize This Pattern