Skip to main content

22. Serialize and Deserialize Binary Tree

hardAsked at Dropbox

Convert a binary tree to a string and back without losing structure — Dropbox uses an analogous serialization format to persist its file-system snapshot trees to disk for offline access and crash recovery.

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 serialization format. A TreeNode has integer val, left, and right fields.

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 produces a string representation; deserialize reconstructs the identical tree.

Example 2

Input
root = []
Output
[]

Approaches

1. BFS level-order

Serialize using a queue; emit each node's value (or '#' for null) level by level. Deserialize by rebuilding the queue and assigning left/right children from the token stream.

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

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

Tradeoff:

2. DFS pre-order

Serialize with recursive pre-order traversal, emitting '#' for null. Deserialize by consuming tokens from a pointer, recursively rebuilding left then right subtrees.

Time
O(n)
Space
O(n)
function serialize(root) {
  const result = [];
  function dfs(node) {
    if (!node) { result.push('#'); return; }
    result.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return result.join(',');
}

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

Tradeoff:

Dropbox-specific tips

Dropbox interviewers specifically probe the format choice: why pre-order works without ambiguity (the '#' markers carry enough structure), while in-order alone does not. Be prepared to whiteboard which traversals are uniquely reconstructible and why — it shows you understand the information theory behind serialization, not just the mechanics.

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

Practice these live with InterviewChamp.AI →