Marauder Bot

Problem

Design a way to turn a binary tree into a string (serialize) and later rebuild an equivalent tree from that string (deserialize), so the round trip reproduces the tree's exact structure and node values.

Example. For a tree with root 1, right child 2, whose own children are 3 and 4, a serialization might read as the sequence 1, null, 2, 3, 4, recording both the values present and where a child is missing.

Key idea

Storing only node values, say from an inorder traversal, is not enough: many different tree shapes can share the same values in the same order, so shape is lost. The fix is to record a placeholder wherever a child pointer is empty, not just the nodes that exist.

A preorder traversal does this cleanly: write the node's value, then recurse left, then right, writing a marker such as "null" whenever a child is absent. Because preorder visits a node before its children, and every missing child is recorded, the string uniquely determines one tree. Deserializing replays the same logic: read one token at a time; if it is the null marker, that position stays empty, otherwise create a node and fill in its left then right child from the tokens that follow.

Solution

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function serialize(root: TreeNode | null): string {
  const tokens: string[] = [];

  function write(node: TreeNode | null): void {
    if (node === null) {
      // Record missing children explicitly, so tree shape isn't lost.
      tokens.push('null');
      return;
    }
    // Preorder: value first, then left subtree, then right subtree.
    tokens.push(String(node.val));
    write(node.left);
    write(node.right);
  }

  write(root);
  return tokens.join(',');
}

function deserialize(data: string): TreeNode | null {
  const tokens = data.split(',');
  let index = 0;

  function read(): TreeNode | null {
    // A shared index advances across recursive calls, consuming tokens in the order they were written.
    const token = tokens[index];
    index++;

    if (token === 'null') {
      return null;
    }

    const node = new TreeNode(Number(token));
    node.left = read();
    node.right = read();
    return node;
  }

  return read();
}

Complexity

Time: O(n). Serialization and deserialization each write or read one token per node and per null pointer, exactly once.
Space: O(n). The output string, plus O(h) for the recursion stack.

Watch out for

Omitting null markers reintroduces ambiguity: 1, 2, 3 cannot say whether 2 is 1's left or right child.
Choose a delimiter that cannot appear inside a value's own text representation, or token boundaries become ambiguous.
Deserialization must consume tokens in the exact order produced, using a shared index across recursive calls rather than re-scanning from the start each time.

Pattern

This is "preorder traversal with explicit null markers," a general way to flatten a pointer-based tree into an order-preserving string, and it extends to n-ary trees by recording each node's child count.

Serialize and Deserialize Binary Tree