Tree serialize / deserialize

O(n)

Encode a tree into a string (or array) that records every child, including missing ones with a null marker, so the exact same shape can be rebuilt from it later.

Signals

serialize a tree to a string and deserialize it backrebuild the exact same shape, not just the same valuesencode/decode wording, design a codec for a treenull/None markers for missing childrenstore or transmit a tree (network transfer, file, cache)

Template

function serialize(node) {
    if (!node) return "#";
    return `${node.val},${serialize(node.left)},${serialize(node.right)}`;
}
function deserialize(data) {
    const vals = data.split(",");
    let i = 0;
    function build() {
        if (vals[i] === "#") { i++; return null; }
        const node = { val: Number(vals[i++]), left: null, right: null };
        node.left = build();
        node.right = build();
        return node;
    }
    return build();
}

Looks similar, isn't

Tree traversal: A plain traversal only visits values in some order and throws the shape away once it is done. Serialize/deserialize records explicit null markers for missing children so the exact structure, not just the values, can be rebuilt.

n nodes -> O(n) time and O(n) output length: a preorder walk with explicit null markers records the whole shape in one linear pass and rebuilds it in another.

Learn this pattern