Frontend Beauty
ESC

Type to search the knowledge base.

Serialize Deserialize Binary Tree

Encode a binary tree to a string and rebuild it — preorder with null markers or BFS level order.

advanced3 min read
  • dsa
  • tree
  • interview
  • Google
  • Meta

The problem

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the same tree structure and values.

    1
   / \
  2   3
     / \
    4   5
// e.g. preorder: "1,2,#,#,3,4,#,#,5,#,#"

Any reversible format works. Interviewers care that nulls are represented so shape is unambiguous.

Node shape

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;
  }
}

Brute-ish: JSON of nested objects

JSON.stringify a recursive object — works in JS but feels like cheating; also need a custom walk for interview signal.

Optimal: preorder + null sentinels

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

function deserialize(data: string): TreeNode | null {
  const parts = data.split(",");
  let i = 0;
  function dfs(): TreeNode | null {
    const token = parts[i++];
    if (token === "#" || token === undefined) return null;
    const node = new TreeNode(Number(token));
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

BFS level-order variant

function serializeBfs(root: TreeNode | null): string {
  if (!root) return "";
  const q: (TreeNode | null)[] = [root];
  const parts: string[] = [];
  while (q.length) {
    const node = q.shift()!;
    if (!node) {
      parts.push("#");
      continue;
    }
    parts.push(String(node.val));
    q.push(node.left, node.right);
  }
  return parts.join(",");
}

function deserializeBfs(data: string): TreeNode | null {
  if (!data) return null;
  const parts = data.split(",");
  const root = new TreeNode(Number(parts[0]));
  const q: TreeNode[] = [root];
  let i = 1;
  while (q.length && i < parts.length) {
    const node = q.shift()!;
    if (parts[i] !== "#") {
      node.left = new TreeNode(Number(parts[i]));
      q.push(node.left);
    }
    i++;
    if (i < parts.length && parts[i] !== "#") {
      node.right = new TreeNode(Number(parts[i]));
      q.push(node.right);
    }
    i++;
  }
  return root;
}
Time O(n) serialize & deserialize
Space O(n) string + recursion/queue

Edge cases

  • Empty tree
  • Single node
  • Negative values and multi-digit numbers — delimiter required
  • Skewed tree — recursion depth

Common bugs

  • Preorder without null markers → ambiguous trees
  • Forgetting to advance index in deserialize
  • Using split on empty string edge cases
  • Mixing BFS serialize with DFS deserialize

Interview delivery

  1. Need null markers.
  2. Pick preorder DFS or BFS.
  3. Implement both directions.
  4. Round-trip a small tree on the board.
  5. O(n).

Further reading