Skip to main content

25. Serialize and Deserialize Binary Tree

hardAsked at Meta

Convert a binary tree to a string and back — Meta's news-feed comment-thread storage serializes hierarchical tree structures to bytes for transmission and reconstruction at billion-user scale every day.

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

Problem

Design an algorithm to serialize and deserialize a binary tree. Serialization is encoding a tree to a string; deserialization is decoding the string back to the original tree structure. There is no restriction on your format — just ensure decode(encode(tree)) reconstructs the original tree.

Constraints

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

Examples

Example 1

Input
root = [1,2,3,null,null,4,5]
Output
[1,2,3,null,null,4,5]

Explanation: The deserialized tree matches the original structure.

Example 2

Input
root = []
Output
[]

Approaches

1. BFS level-order

Serialize with BFS, recording null placeholders. Deserialize by replaying the queue, attaching left then right children from the encoded values.

Time
O(n)
Space
O(n)
function serialize(root) {
  if (!root) return '[]';
  const queue = [root], res = [];
  while (queue.length) {
    const node = queue.shift();
    if (node) { res.push(node.val); queue.push(node.left, node.right); }
    else res.push('null');
  }
  return '[' + res.join(',') + ']';
}
function deserialize(data) {
  const vals = data.slice(1,-1).split(',');
  if (vals[0] === '' || vals[0] === 'null') return null;
  const root = { val: +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: +vals[i], left: null, right: null }; queue.push(node.left); }
    i++;
    if (i < vals.length && vals[i] !== 'null') { node.right = { val: +vals[i], left: null, right: null }; queue.push(node.right); }
    i++;
  }
  return root;
}

Tradeoff:

2. DFS preorder (optimal)

Serialize with preorder DFS (root, left, right), marking nulls with a sentinel. Deserialize recursively consuming tokens — more compact output, simpler implementation.

Time
O(n)
Space
O(n)
function serialize(root) {
  const tokens = [];
  function dfs(node) {
    if (!node) { tokens.push('#'); return; }
    tokens.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return tokens.join(',');
}
function deserialize(data) {
  const tokens = data.split(',');
  let i = 0;
  function dfs() {
    if (tokens[i] === '#') { i++; return null; }
    const node = { val: +tokens[i++], left: null, right: null };
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

Tradeoff:

Meta-specific tips

Meta loves this problem because it touches system-design thinking: how does Facebook serialize comment trees for caching or cross-datacenter replication? Start with the DFS approach for clarity, but mention that BFS level-order output is more human-readable and easier to debug in production logs. Interviewers may ask about handling large trees — discuss chunked streaming serialization.

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

Practice these live with InterviewChamp.AI →