Skip to main content

24. Serialize and Deserialize Binary Tree

hardAsked at Wix

Convert a binary tree to a portable string and restore it exactly — Wix stores the entire site element tree as a serialized document, so this problem directly exercises the persistence and hydration logic at the heart of their editor.

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 identical tree. There is no restriction on the format — choose any scheme that allows full round-trip fidelity.

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
[1,2,3,null,null,4,5]

Explanation: Serialize then deserialize must reproduce the same tree

Example 2

Input
root = []
Output
[]

Approaches

1. BFS level-order (standard format)

BFS, emitting 'null' for missing children. Deserialize by rebuilding level-by-level using a queue of parent nodes.

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) {
      result.push('null');
      continue;
    }
    result.push(String(node.val));
    queue.push(node.left);
    queue.push(node.right);
  }
  return result.join(',');
}

function deserialize(data) {
  if (data === 'null') return null;
  const vals = data.split(',');
  const root = { val: Number(vals[0]), left: null, right: null };
  const queue = [root];
  let i = 1;
  while (queue.length && i < vals.length) {
    const node = queue.shift();
    if (vals[i] !== 'null') {
      node.left = { val: Number(vals[i]), left: null, right: null };
      queue.push(node.left);
    }
    i++;
    if (i < vals.length && vals[i] !== 'null') {
      node.right = { val: Number(vals[i]), left: null, right: null };
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

Tradeoff:

2. DFS preorder (self-delimiting)

DFS preorder emits val then recurses left then right; null nodes emit a sentinel. Deserialize by consuming tokens in the same preorder walk — no breadth tracking needed.

Time
O(n)
Space
O(n) for the call stack on a skewed tree
function serialize(root) {
  const parts = [];
  function dfs(node) {
    if (!node) { parts.push('#'); return; }
    parts.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return parts.join(',');
}

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

Tradeoff:

Wix-specific tips

Wix interviewers care as much about the format choice as the code — they want to know why you picked your encoding. DFS preorder is a strong pick because it's self-delimiting: the structure is implicit in the traversal order, no length fields or index metadata needed. That principle — encoding structure in order, not in metadata — maps to how Wix represents nested page sections in their document model.

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 Wix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →