Serialize and Deserialize Binary Tree

Problem Description

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Examples

Constraints

• The number of nodes in the tree is in the range [0, 10⁴].
• -1000 ≤ Node.val ≤ 1000

Reconstructing Structure with Null Node Markers

If you only output node values during traversal, you lose the shape of the tree. For example, [1, 2] could represent a root 1 with a left child 2, or a root 1 with a right child 2.

To reconstruct the tree structure uniquely, you must record empty nodes. We can use a special character like N or # to represent a null node.

If we use pre-order traversal (root, left, right), the serialized string starts with the root. When deserializing, we read the current value. If it is N, we return null. Otherwise, we create a new node, and recursively build its left child first, then its right child, matching the pre-order insertion order.

Solution 1: Pre-Order Traversal with Delimiters

Use a comma-delimited string of node values, inserting N for null pointers.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("N,");
            return;
        }
        sb.append(node.val).append(",");
        buildString(node.left, sb);
        buildString(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return buildTree(nodes);
    }

    private TreeNode buildTree(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("N")) return null;

        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
        return node;
    }
}

class Codec:
    def serialize(self, root: TreeNode) -> str:
        result = []

        def build_string(node):
            if not node:
                result.append("N")
                return
            result.append(str(node.val))
            build_string(node.left)
            build_string(node.right)

        build_string(root)
        return ",".join(result)

    def deserialize(self, data: str) -> TreeNode:
        vals = data.split(",")
        idx = 0

        def build_tree():
            nonlocal idx
            val = vals[idx]
            idx += 1
            if val == "N":
                return None

            node = TreeNode(int(val))
            node.left = build_tree()
            node.right = build_tree()
            return node

        return build_tree()

#include <string>
#include <sstream>
#include <vector>

class Codec {
private:
    void serializeHelper(TreeNode* node, std::stringstream& ss) {
        if (!node) {
            ss << "N,";
            return;
        }
        ss << node->val << ",";
        serializeHelper(node->left, ss);
        serializeHelper(node->right, ss);
    }

    TreeNode* deserializeHelper(std::stringstream& ss) {
        std::string val;
        if (!std::getline(ss, val, ',')) return nullptr;
        if (val == "N") return nullptr;

        TreeNode* node = new TreeNode(std::stoi(val));
        node->left = deserializeHelper(ss);
        node->right = deserializeHelper(ss);
        return node;
    }

public:
    // Encodes a tree to a single string.
    std::string serialize(TreeNode* root) {
        std::stringstream ss;
        serializeHelper(root, ss);
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(std::string data) {
        std::stringstream ss(data);
        return deserializeHelper(ss);
    }
};

Complexity Analysis:

• Time Complexity: O(n) for both serialization and deserialization. We visit each node and null pointer exactly once.
• Space Complexity: O(n). The serialized string holds n numbers and n null markers. The recursion stack uses at most O(h) space.

Where it breaks: If tree nodes contain values with commas or delimiter characters, parsing splits will corrupt the payload. Using a clear non-digit delimiter (like a comma) works because node values are guaranteed to be integers.

Common Mistakes

• Forgetting delimiters between node values. If you output 123 for root 1 with children 2 and 3, you cannot tell if the root was 12 with child 3, or root 1 with child 23.
• Deserializing the left and right subtrees in the wrong order. Deserialization must match the serialization order. If you serialized left before right, you must build the left child before the right child.
• Incorrectly advancing the string parsing pointer. Using queue structures or global index parameters (like Python’s nonlocal idx) ensures you consume elements sequentially.

Frequently Asked Questions

Can we serialize using Breadth-First Search (BFS)? Yes. You can serialize level by level using a queue, appending node values and null markers. Deserialization also uses a queue: you instantiate the root, push it to the queue, and then match the incoming tokens in pairs to reconstruct children.

How does this handle trees with negative values? The values are integers, which can be negative. String conversions handle negative signs naturally (e.g. "-10").

What does this problem test in interviews? It tests your capability to design data transmission payloads, manage parser indices, and coordinate encoding and decoding processes.

← All Problems