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.

Sources: Wikipedia: Serialization

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

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

function serialize(node: TreeNode | null): string {
    if (!node) return "#";
    return `${node.val},${serialize(node.left)},${serialize(node.right)}`;
}

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

def serialize(node):
    if not node:
        return "#"
    return f"{node.val},{serialize(node.left)},{serialize(node.right)}"

def deserialize(data):
    vals = iter(data.split(","))
    def build():
        val = next(vals)
        if val == "#":
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node
    return build()

function serialize(?TreeNode $node): string {
    if ($node === null) return "#";
    return $node->val . "," . serialize($node->left) . "," . serialize($node->right);
}
function deserialize(array &$vals): ?TreeNode {
    $val = array_shift($vals);
    if ($val === "#") return null;
    $node = new TreeNode((int) $val);
    $node->left = deserialize($vals);
    $node->right = deserialize($vals);
    return $node;
}

    public static String serialize(TreeNode node) {
        if (node == null) return "#";
        return node.val + "," + serialize(node.left) + "," + serialize(node.right);
    }

    public static TreeNode deserialize(String data) {
        return build(new ArrayDeque<>(Arrays.asList(data.split(","))));
    }

    private static TreeNode build(Deque<String> vals) {
        String val = vals.poll();
        if (val == null || val.equals("#")) return null;
        TreeNode node = new TreeNode();
        node.val = Integer.parseInt(val);
        node.left = build(vals);
        node.right = build(vals);
        return node;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static string Serialize(TreeNode node) {
        if (node == null) return "#";
        return node.val + "," + Serialize(node.left) + "," + Serialize(node.right);
    }

    public static TreeNode Deserialize(string data) {
        return Build(new Queue<string>(data.Split(',')));
    }

    private static TreeNode Build(Queue<string> vals) {
        string val = vals.Dequeue();
        if (val == "#") return null;
        var node = new TreeNode();
        node.val = int.Parse(val);
        node.left = Build(vals);
        node.right = Build(vals);
        return node;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

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?

Use Tree serialize / deserialize when the problem statement says “serialize a tree to a string and deserialize it back”, “rebuild the exact same shape, not just the same values” or “encode/decode wording, design a codec for a tree”. A solution built on it usually runs in O(n).

• •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)

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Tree serialize / deserialize confused with?

Tree serialize / deserialize is most often confused with Tree traversal, Recursion, Graph BFS / DFS and Binary search tree.

• 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

  Index arithmetic 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?

Interview problems solved with Tree serialize / deserialize include Serialize and deserialize a binary tree, Serialize and deserialize a BST, Serialize and deserialize an n-ary tree, Build a tree from preorder and inorder, Build a tree from preorder and postorder, Find duplicate subtrees and Encode and decode strings.

• 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?

The target complexity of Tree serialize / deserialize is O(n).

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