# Serialize and Deserialize Binary Tree

> How to solve Serialize and Deserialize Binary Tree: encode a preorder walk with explicit null markers to preserve tree shape.

- Difficulty: Hard
- Category: Trees
- Topics: Tree, DFS, BFS, Design
- Published 2026-08-21

## Problem

Design a way to turn a binary tree into a string (serialize) and later rebuild an equivalent tree from that string (deserialize), so the round trip reproduces the tree's exact structure and node values.

**Example.** For a tree with root `1`, right child `2`, whose own children are `3` and `4`, a serialization might read as the sequence `1, null, 2, 3, 4`, recording both the values present and where a child is missing.

## Key idea

Storing only node values, say from an inorder traversal, is not enough: many different tree shapes can share the same values in the same order, so shape is lost. The fix is to record a placeholder wherever a child pointer is empty, not just the nodes that exist.

A preorder traversal does this cleanly: write the node's value, then recurse left, then right, writing a marker such as "null" whenever a child is absent. Because preorder visits a node before its children, and every missing child is recorded, the string uniquely determines one tree. Deserializing replays the same logic: read one token at a time; if it is the null marker, that position stays empty, otherwise create a node and fill in its left then right child from the tokens that follow.

## Solution

```typescript
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function serialize(root: TreeNode | null): string {
  const tokens: string[] = [];

  function write(node: TreeNode | null): void {
    if (node === null) {
      // Record missing children explicitly, so tree shape isn't lost.
      tokens.push('null');
      return;
    }
    // Preorder: value first, then left subtree, then right subtree.
    tokens.push(String(node.val));
    write(node.left);
    write(node.right);
  }

  write(root);
  return tokens.join(',');
}

function deserialize(data: string): TreeNode | null {
  const tokens = data.split(',');
  let index = 0;

  function read(): TreeNode | null {
    // A shared index advances across recursive calls, consuming tokens in the order they were written.
    const token = tokens[index];
    index++;

    if (token === 'null') {
      return null;
    }

    const node = new TreeNode(Number(token));
    node.left = read();
    node.right = read();
    return node;
  }

  return read();
}
```

## Complexity

- **Time:** O(n). Serialization and deserialization each write or read one token per node and per null pointer, exactly once.
- **Space:** O(n). The output string, plus O(h) for the recursion stack.

## Watch out for

- Omitting null markers reintroduces ambiguity: `1, 2, 3` cannot say whether `2` is `1`'s left or right child.
- Choose a delimiter that cannot appear inside a value's own text representation, or token boundaries become ambiguous.
- Deserialization must consume tokens in the exact order produced, using a shared index across recursive calls rather than re-scanning from the start each time.

## Pattern

This is "preorder traversal with explicit null markers," a general way to flatten a pointer-based tree into an order-preserving string, and it extends to n-ary trees by recording each node's child count.

---

Canonical URL: https://www.marauderbot.com/questions/serialize-and-deserialize-binary-tree
