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

Time Complexity: Serialize and Deserialize Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to save and restore a binary tree changes as the tree grows.

How does the work increase when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function serialize(root) {
  if (!root) return '';
  return root.val + ',' + serialize(root.left) + serialize(root.right);
}

function deserialize(data) {
  const nodes = data.split(',');
  function build() {
    if (!nodes.length) return null;
    const val = nodes.shift();
    if (val === '') return null;
    const node = { val: Number(val), left: build(), right: build() };
    return node;
  }
  return build();
}
    

This code saves a binary tree to a string and rebuilds it back from that string using preorder traversal.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of nodes (n) grows, the work grows roughly the same amount because each node is processed once.

Input Size (n)	Approx. Operations
10	About 10 visits to nodes
100	About 100 visits to nodes
1000	About 1000 visits to nodes

Pattern observation: The time grows linearly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Serialization or deserialization takes more than linear time because of string operations or recursion overhead."

[OK] Correct: Each node is visited once, and string operations like split or concatenation happen proportional to n, so overall time stays linear.

Interview Connect

Understanding this helps you explain how tree data can be saved and restored efficiently, a common skill in coding interviews and real projects.

Self-Check

"What if we changed the traversal order in serialization from preorder to inorder? How would the time complexity change?"