---
title: "Tree serialize / deserialize"
url: https://algopath.pro/patterns/tree-serialize
language: en
summary: "Write a tree out as one flat string, then rebuild it exactly. The markers for the missing children are what make it work."
updated: 2026-08-24
---

# Tree serialize / deserialize

Write a tree out as one flat string, then rebuild it exactly. The markers for the missing children are what make it work.

## 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.

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

## When should you use Tree serialize / deserialize?

- 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.

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

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

## 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.

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

## 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.

## JavaScript

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

## Python

```python
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()
```

## PHP

```php
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;
}
```