Tree serialize / deserialize

How does Tree serialize / deserialize work?

Pick one traversal order and stay with it. Pre-order is the easiest to rebuild from.

Write each node's value as you visit it. Separate the values with a delimiter.

Write a marker for every missing child too. Without those markers the shape is lost.

To rebuild, read the tokens in that same order. Each token becomes exactly one node.

A marker means an empty child, so return at once. A value builds a node and reads its two children.

Both halves consume the tokens in the same order. That is why the shape comes back exactly.

1. write 1The tree is 1 with a left child 2. Pre-order writes the node first.
2. write 2The left child is written next.
3. write #, #Node 2 has no children. Two markers record that.
4. write #Node 1 has no right child either.
5. 1,2,#,#,#Five tokens for two nodes. The markers carry the shape.

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();
}

A worked example of Tree serialize / deserialize

Serialise and rebuild a binary tree

Turn a binary tree into a string. Then turn that string back into the same tree.

The rebuilt tree has to match the original node for node.

Write it in pre-order, with a hash for every empty child.

Read it back with a cursor over the tokens. A hash returns null, anything else builds a node.

function serialize(root) {
    const out = [];

    (function write(node) {
        if (!node) {
            out.push("#"); // the marker is what preserves the shape
            return;
        }
        out.push(String(node.val));
        write(node.left);
        write(node.right);
    })(root);

    return out.join(",");
}

function deserialize(data) {
    const tokens = data.split(",");
    let i = 0;

    function read() {
        const token = tokens[i++];
        if (token === "#") return null;

        const node = new TreeNode(Number(token));
        node.left = read();   // left must be consumed before right
        node.right = read();
        return node;
    }

    return read();
}

When should you use Tree serialize / deserialize?

These phrases in a problem statement point here:

• •serialize a tree to a string and deserialize it back
• •rebuild the exact same shape, not just the same values
• •encode/decode wording, design a codec for a tree
• •null/None markers for missing children
• •store or transmit a tree (network transfer, file, cache)

What is Tree serialize / deserialize confused with?

• Tree traversal: A traversal only reads the tree. Serialising also has to record where children are missing.
• Recursion: Both halves are ordinary recursion. The real work is agreeing on a format.
• Graph BFS / DFS: A level-order format is equally valid, and most puzzle sites use it. The reader has to match the writer.
• Binary search tree: A search tree needs no markers, because the order fixes the shape. A plain tree does need them.

Common mistakes with Tree serialize / deserialize

• Leaving out the markers

  Pre-order alone cannot say where a child was missing. Two different trees then give one string.

• Picking a delimiter the data contains

  Values can be negative or have several digits. Choose a character the values cannot hold.

• Rebuilding by index arithmetic

  That only works on a complete tree. Use a moving cursor over the tokens instead.

• Reading the children in the wrong order

  The reader has to consume left before right. Some languages evaluate arguments right to left.

Which interview problems use Tree serialize / deserialize?

• Serialize and deserialize a binary tree: The plain form, with a marker per empty child.
• Serialize and deserialize a BST: No markers needed, since the order fixes the shape.
• Serialize and deserialize an n-ary tree: Write the child count beside each value.
• Build a tree from preorder and inorder: Two traversals pin the shape without markers.
• Build a tree from preorder and postorder: The same idea, with one ambiguous case.
• Find duplicate subtrees: Serialise each subtree and count the strings.
• Encode and decode strings: The same length-prefix idea, applied to text.

What is the time and space complexity of Tree serialize / deserialize?

O(n)

n nodes give O(n) time and O(n) output. Each node and each missing child is written once.