Serialize and Deserialize Binary Tree

Examples

Input: root = [1,2,3,null,null,4,5]
Output: deserialize(serialize(root)) reproduces [1,2,3,null,null,4,5]

The exact string format is up to you — what matters is that the shape and values survive the round trip.

Input: root = []
Output: deserialize(serialize(root)) reproduces []

An empty tree must round-trip to an empty tree too.

Constraints

• The number of nodes is in the range [0, 10^4].

• Node values are in the range [-1000, 1000].

Approach

The core trick is encoding null children explicitly, as real entries in the output, rather than just omitting them — that's what makes the shape of the tree recoverable, not just its values.

Two traversal orders both work well for this: a level-order (BFS) traversal that records a child slot even when it's empty, or a preorder (DFS) traversal that does the same. Either one can be replayed in the same order during deserialization to rebuild the identical structure, one node (or "empty slot") at a time.

Solutions

Level-Order (BFS) with Null Markers

Serialize by doing a breadth-first walk with a queue: for every node dequeued, record its value (or "null" if the slot is empty), and if it wasn't empty, enqueue its two children (which may themselves be null).

Deserialize by reversing the process: read the first value as the root, then walk through the rest of the string in order, using a queue of "nodes still waiting for their two children" to know where each subsequent value belongs.

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

function serialize(root) {
  if (root === null) return "null";

  const values = [];
  const queue = [root];

  while (queue.length > 0) {
    const node = queue.shift();
    if (node === null) {
      values.push("null");
    } else {
      values.push(String(node.val));
      queue.push(node.left);
      queue.push(node.right);
    }
  }

  return values.join(",");
}

function deserialize(data) {
  const values = data.split(",");
  if (values[0] === "null") return null;

  const root = new TreeNode(Number(values[0]));
  const queue = [root];
  let index = 1;

  while (queue.length > 0) {
    const node = queue.shift();

    const leftVal = values[index++];
    if (leftVal !== "null") {
      node.left = new TreeNode(Number(leftVal));
      queue.push(node.left);
    }

    const rightVal = values[index++];
    if (rightVal !== "null") {
      node.right = new TreeNode(Number(rightVal));
      queue.push(node.right);
    }
  }

  return root;
}

Time: O(n) for both serialize and deserialize · Space: O(n) — the output string and the queue

Preorder (DFS) with Null Markers

Serialize with a preorder traversal (visit the node itself first, then recurse left, then right), writing "null" whenever a child is missing. Because null markers are written for every missing child, the resulting sequence unambiguously describes the tree's shape.

Deserialize by reading that same sequence back in order with a single shared position pointer: the next token is always either "null" (this subtree is empty) or a value (build a node, then recursively read its left subtree, then its right subtree from the tokens that follow). This is equally efficient, and some find it a little more direct to reason about than the BFS version, since serialize and deserialize mirror each other line for line.

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

function serialize(root) {
  const values = [];

  function dfs(node) {
    if (node === null) {
      values.push("null");
      return;
    }
    values.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);
  return values.join(",");
}

function deserialize(data) {
  const values = data.split(",");
  let index = 0;

  function dfs() {
    const val = values[index];
    index++;
    if (val === "null") return null;

    const node = new TreeNode(Number(val));
    node.left = dfs();
    node.right = dfs();
    return node;
  }

  return dfs();
}

Time: O(n) for both serialize and deserialize · Space: O(n) — the output string, plus O(h) recursion stack