Q50: Serialize and Deserialize Binary Tree

Design an algorithm to serialize a binary tree into a single string and deserialize that string back into the original binary tree structure.

Pre-Order DFS Tree Serialization

function serialize(root) {
  const result = [];
  function dfs(node) {
    if (!node) {
      result.push('N');
      return;
    }
    result.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return result.join(',');
}

function deserialize(data) {
  const tokens = data.split(',');
  let index = 0;
  
  function dfs() {
    if (tokens[index] === 'N') {
      index++;
      return null;
    }
    const node = { val: parseInt(tokens[index++], 10), left: null, right: null };
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

💡 serialize performs pre-order DFS adding node values or 'N' for nulls into a CSV string. deserialize consumes tokens sequentially, creating node objects recursively.

Key Takeaways

Pre-order traversal DFS converts tree to comma-separated string, using sentinel tokens (e.g. 'N') for null nodes.
Deserialization reconstructs nodes sequentially from queue tokens.

Knowledge Check

Why are explicit null markers ('N') required in pre-order tree serialization?

Q50: Serialize and Deserialize Binary Tree

STAY UPDATED WITH BYTES!