Skip to main content

297. Serialize and Deserialize Binary Tree

hardAsked at Snap

Snap persists user story-collection hierarchies to disk between app launches — serialize/deserialize is the interview form of the codec their persistence layer implements.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree structure. There is no restriction on your format — the only requirement is that serialize(deserialize(s)) == s and deserialize(serialize(tree)) produces the original tree.

Constraints

  • The number of nodes is in the range [0, 10^4]
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [1,2,3,null,null,4,5]
Output
serialize → "1,2,null,null,3,4,null,null,5,null,null"; deserialize → same tree

Example 2

Input
root = []
Output
serialize → "null"; deserialize → null

Approaches

1. BFS level-order codec

Serialize: BFS, write each node's value or 'null' comma-separated. Deserialize: split string, BFS reconstruct using a queue of parent nodes. Mirrors JSON representation — easy to debug.

Time
O(n)
Space
O(n)
function serialize(root) {
  if (!root) return 'null';
  const result = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (node === null) { result.push('null'); continue; }
    result.push(node.val);
    queue.push(node.left);
    queue.push(node.right);
  }
  return result.join(',');
}
function deserialize(data) {
  const vals = data.split(',');
  if (vals[0] === 'null') return null;
  const root = new TreeNode(parseInt(vals[0]));
  const queue = [root];
  let i = 1;
  while (queue.length && i < vals.length) {
    const node = queue.shift();
    if (vals[i] !== 'null') {
      node.left = new TreeNode(parseInt(vals[i]));
      queue.push(node.left);
    }
    i++;
    if (i < vals.length && vals[i] !== 'null') {
      node.right = new TreeNode(parseInt(vals[i]));
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

Tradeoff:

2. Preorder DFS codec

Serialize: preorder DFS, write each node or '#' for null. Deserialize: use an index pointer or iterator into the token array; each recursive call consumes exactly one token. Compact for balanced trees, natural for recursive thinkers.

Time
O(n)
Space
O(n) call stack
function serialize(root) {
  const parts = [];
  function dfs(node) {
    if (!node) { parts.push('#'); return; }
    parts.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return parts.join(',');
}
function deserialize(data) {
  const vals = data.split(',');
  let idx = 0;
  function dfs() {
    if (vals[idx] === '#') { idx++; return null; }
    const node = new TreeNode(parseInt(vals[idx++]));
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

Tradeoff:

Snap-specific tips

Snap's persistence team favors the BFS codec because it's easier to diff (same shape as JSON). In the interview, pick one approach and own it completely — don't switch halfway. A common trap: forgetting that '#' nulls must be encoded or you lose structural information needed for deserialization.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Serialize and Deserialize Binary Tree and other Snap interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →