Serialize and Deserialize Binary Tree in DSA C++ - Time & Space Complexity

Time Complexity: Serialize and Deserialize Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to convert a binary tree into a string and back.

How does the time needed grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void serialize(TreeNode* root, ostringstream &out) {
    if (!root) {
        out << "# ";
        return;
    }
    out << root->val << ' ';
    serialize(root->left, out);
    serialize(root->right, out);
}

TreeNode* deserialize(istringstream &in) {
    string val;
    in >> val;
    if (val == "#") return nullptr;
    TreeNode* node = new TreeNode(stoi(val));
    node->left = deserialize(in);
    node->right = deserialize(in);
    return node;
}
    

This code converts a binary tree to a string and back using preorder traversal with markers for null nodes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive traversal of each node in the tree.
• How many times: Each node is visited exactly once during serialization and once during deserialization.

How Execution Grows With Input

As the number of nodes in the tree grows, the time to serialize and deserialize grows proportionally.

Input Size (n)	Approx. Operations
10	About 10 visits plus null markers
100	About 100 visits plus null markers
1000	About 1000 visits plus null markers

Pattern observation: The operations grow linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to serialize or deserialize grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "Serialization takes constant time because it just converts to a string."

[OK] Correct: The code must visit every node to record its value or null marker, so time grows with tree size.

Interview Connect

Understanding this helps you explain how tree data can be saved and restored efficiently, a common real-world need.

Self-Check

"What if we used level-order traversal instead of preorder? How would the time complexity change?"