Skip to main content

26. Serialize and Deserialize Binary Tree

hardAsked at CircleCI

Design codec functions for binary tree serialization, mirroring CircleCI's pipeline configuration serialization and deserialization for distributed job state persistence.

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

Problem

Design an algorithm to serialize a binary tree to a string and deserialize the string back to the original tree structure. There is no restriction on format — choose any that works correctly.

Constraints

  • Number of nodes in [0, 10^4]
  • Node values in [-1000, 1000]

Examples

Example 1

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

Example 2

Input
root = []
Output
[]

Approaches

1. BFS level-order

Serialize using BFS, including null markers; deserialize by rebuilding level by level with a queue.

Time
O(n)
Space
O(n)
const serialize = root => {
  if (!root) return '[]';
  const res = [], q = [root];
  while (q.length) {
    const n = q.shift();
    res.push(n ? n.val : null);
    if (n) { q.push(n.left); q.push(n.right); }
  }
  return JSON.stringify(res);
};
const deserialize = data => {
  const vals = JSON.parse(data);
  if (!vals.length || vals[0] === null) return null;
  const root = { val: vals[0], left: null, right: null };
  const q = [root]; let i = 1;
  while (q.length && i < vals.length) {
    const n = q.shift();
    if (vals[i] != null) { n.left = { val: vals[i], left: null, right: null }; q.push(n.left); } i++;
    if (i < vals.length && vals[i] != null) { n.right = { val: vals[i], left: null, right: null }; q.push(n.right); } i++;
  }
  return root;
};

Tradeoff:

2. DFS preorder with null markers

Serialize via DFS preorder, using a sentinel for nulls; deserialize by consuming tokens recursively. Simpler code and works well for deep trees with sparse null nodes.

Time
O(n)
Space
O(n)
const 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(',');
};
const deserialize = data => {
  const tokens = data.split(',');
  let idx = 0;
  function dfs() {
    if (tokens[idx] === '#') { idx++; return null; }
    const node = { val: +tokens[idx++], left: null, right: null };
    node.left = dfs(); node.right = dfs();
    return node;
  }
  return dfs();
};

Tradeoff:

CircleCI-specific tips

CircleCI relates this to pipeline config persistence across restarts — demonstrate awareness of format stability (tokens vs JSON), discuss versioning implications, and mention that the DFS approach produces more compact output for sparse trees.

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

Practice these live with InterviewChamp.AI →