07. Serialize and Deserialize Binary Tree

Difficulty:HardPattern:Pre-Order DFS SerializationTime:O(n)Space:O(n)

Design an algorithm to serialize and deserialize a binary tree into a string format and reconstruct the exact original tree structure.

How It Works & Algorithmic Design

Solves using Pre-Order Traversal with Sentinel Markers:

Serialization: Perform DFS pre-order traversal. For each non-null node append node.val + ','. For null nodes append 'null,'.
Deserialization: Split serialized string by ',' into a list/queue of tokens.
- Read next token: if token equals 'null', return null.
- Otherwise, create node = new TreeNode(Number(token)).
- node.left = deserialize().
- node.right = deserialize().
- Return node.

Why This Approach Works Best

Pre-order sentinel traversal uniquely identifies tree structure without needing both In-Order and Pre-Order arrays, executing in $O(n)$ time and $O(n)$ space.

Example Walkthrough

Input Tree: [1, 2, 3, null, null, 4, 5]

Binary tree.

Serialized String: "1,2,null,null,3,4,null,null,5,null,null,"

Pre-order string with sentinel nulls.

Deserialized Result: Reconstructed identical binary tree.

Tree reference match.

Answer: Tree Serialization & Deserialization implementation

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

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

💡 Convert tree nodes to pre-order comma-separated string and reconstruct iteratively via token queue.

Key Takeaways

Sentinel null markers retain structural information during serialization.
Pre-order token streams can be parsed using simple recursive queue consumers.
Linear execution time $O(n)$.