Serialize / Deserialize a Binary Tree

March 2026 · 7 min read

The Problem

Serialization converts a tree into a linear format (string, array, byte stream) that can be stored or transmitted. Deserialization reconstructs the original tree from that format, the tree must be identical, including structure and values.

This is a practical problem: databases store tree-structured data (JSON, XML), distributed systems send tree structures over the wire, and competitive programming problems often give trees as serialized input.

Approach 1: Preorder with Null Markers

The simplest approach: do a preorder traversal (root, left, right) and write each node's value. When we hit a null pointer, write a sentinel marker (like #). This encoding is unambiguous, given the serialized string, there's exactly one tree that produces it.

Why Preorder?

Because the root comes first, which makes deserialization natural: read the first value, that's the root. Then recursively build the left subtree from the next chunk, then the right subtree.

Why Null Markers?

Without them, we can't distinguish between different tree shapes that have the same preorder values. The null markers encode the structure. Consider two trees with preorder [1, 2]:

  Tree A:   1        Tree B:   1
           /                    \
          2                      2

Preorder with nulls:
  A: "1,2,#,#,#,"
  B: "1,#,2,#,#,"
Now they're distinguishable!

Serialize: Tree → String

std::string serialize(TreeNode* root) {
    if (!root) return "#,";           // null marker
    return std::to_string(root->val) + "," +
           serialize(root->left) +     // left subtree
           serialize(root->right);     // right subtree
}

For the tree [1, 2, 3, null, null, 4, 5], this produces: "1,2,#,#,3,4,#,#,5,#,#,"

Deserialize: String → Tree

TreeNode* deserialize(std::istringstream& stream) {
    std::string token;
    if (!std::getline(stream, token, ',') || token == "#")
        return nullptr;                // hit a null marker
    auto* node = new TreeNode(std::stoi(token));
    node->left  = deserialize(stream);  // build left subtree
    node->right = deserialize(stream);  // build right subtree
    return node;
}

The stream is consumed left-to-right, exactly matching the preorder sequence. Each recursive call reads the next token from where the previous call left off, the stream acts as a shared cursor.

Time: O(n) for both directions.
Space: O(n) for the string, O(h) for recursion stack.

Approach 2: Level-Order (BFS) Serialization

This is what LeetCode uses. Write nodes level by level, using null for missing children:

std::string serializeBFS(TreeNode* root) {
    if (!root) return "[]";
    std::string result = "[";
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        auto* node = q.front(); q.pop();
        if (node) {
            result += std::to_string(node->val) + ",";
            q.push(node->left);
            q.push(node->right);
        } else {
            result += "null,";
        }
    }
    // Trim trailing nulls for compactness
    result.back() = ']';
    return result;
}

Deserialization uses a queue too: read the root, then for each node in the queue, read its left and right children from the stream.

Alternative Approaches

• Preorder + Inorder (no null markers): Two traversals together uniquely define a tree. Used when you can't afford null markers (compact encoding). Requires O(n) extra space for the inorder map.
• Parenthesized format: 1(2()())(3(4()())(5()())), explicit nesting. Self-documenting but verbose.
• Binary encoding: For space efficiency, write values as fixed-width binary with 1-bit flags for null. Useful in database B-tree page serialization.

When to Use Which