Skip to main content

31. Serialize and Deserialize Binary Tree

hardAsked at Lyft

Encode and reconstruct a binary tree via a string — Lyft applies the same BFS-serialization contract to persist driver-preference decision trees to its configuration store and reload them across service restarts without losing structure.

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

Problem

Design an algorithm to serialize and deserialize a binary tree. Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Constraints

  • The number of nodes in the tree 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: After serialize then deserialize, the original tree structure must be restored exactly.

Example 2

Input
root = []
Output
[]

Approaches

1. BFS level-order

Serialize via BFS, emitting 'null' for missing children. Deserialize by re-running BFS: assign left/right children from the queue of values, skipping nulls.

Time
O(n)
Space
O(n)
function serialize(root) {
  if (!root) return '[]';
  const queue = [root];
  const res = [];
  while (queue.length) {
    const node = queue.shift();
    if (!node) { res.push('null'); continue; }
    res.push(node.val);
    queue.push(node.left);
    queue.push(node.right);
  }
  return '[' + res.join(',') + ']';
}

function deserialize(data) {
  const vals = data.slice(1, -1).split(',');
  if (vals[0] === 'null' || vals[0] === '') return null;
  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

Serialize with preorder DFS (root, left, right), emitting '#' for null nodes. Deserialize by consuming tokens in preorder: current value, then recurse for left, then right.

Time
O(n)
Space
O(n)
function serialize(root) {
  const res = [];
  function dfs(node) {
    if (!node) { res.push('#'); return; }
    res.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return res.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 };
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

Tradeoff:

Lyft-specific tips

Lyft frames this problem as a real systems question: 'How would you checkpoint a tree-shaped routing config to Redis and restore it on pod restart?' They want you to choose a format consciously — BFS maps naturally to JSON/level arrays; DFS preorder is more compact and elegant. State your choice and defend it. The DFS solution is cleaner in code; lead with it. Watch the index management in deserialize — advancing i correctly is where candidates slip.

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

Practice these live with InterviewChamp.AI →