Serialize and Deserialize Binary Tree in DSA Typescript - 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 grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function serialize(root: TreeNode | null): string {
  const parts = [];
  function helper(node: TreeNode | null) {
    if (!node) {
      parts.push('#');
      return;
    }
    parts.push(node.val.toString());
    helper(node.left);
    helper(node.right);
  }
  helper(root);
  return parts.join(',');
}

function deserialize(data: string): TreeNode | null {
  const nodes = data.split(',');
  let i = 0;
  function build(): TreeNode | null {
    const val = nodes[i++];
    if (val === '#') return null;
    const node = new TreeNode(parseInt(val));
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}
    

This code turns a binary tree into a string and then rebuilds the tree from that string.

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 work grows proportionally.

Input Size (n)	Approx. Operations
10	About 20 visits (10 nodes during serialize + 10 during deserialize)
100	About 200 visits
1000	About 2000 visits

Pattern observation: The total work doubles but stays directly proportional to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to serialize and deserialize grows linearly with 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 processed once, and string splitting or concatenation happens in a way that overall work stays proportional to the number of nodes.

Interview Connect

Understanding this linear time complexity helps you explain how your solution scales and shows you can reason about recursive tree algorithms clearly.

Self-Check

"What if we used an iterative approach with a queue instead of recursion? How would the time complexity change?"