27. Serialize and Deserialize Binary Tree

hardAsked at Databricks

Encode and reconstruct an arbitrary binary tree through a string — a serialization-format problem Databricks faces when checkpointing execution-plan trees in Delta's query optimizer and persisting MLflow model dependency graphs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. There is no restriction on the format — any scheme that correctly round-trips all trees is acceptable.

Constraints

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

Examples

Example 1

Input

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

Output

serialize: "1,2,null,null,3,4,null,null,5,null,null" (pre-order with null markers), deserialize returns the original tree

Example 2

Input

root = []

Output

""

Approaches

1. BFS level-order

Serialize by BFS, recording null for missing children. Deserialize by replaying BFS. Produces a compact, human-readable format similar to LeetCode's own representation.

Time: O(n)
Space: O(n)

function serialize(root) {
  if (!root) return '';
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    if (node === null) { 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) 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 > 0 && 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 pre-order with null sentinels

Pre-order DFS naturally reconstructs a unique tree when null leaves are recorded. Deserialize by consuming tokens from a pointer into the split array.

Time: O(n)
Space: O(n)

function serialize(root) {
  const parts = [];
  function dfs(node) {
    if (!node) { parts.push('X'); return; }
    parts.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return parts.join(',');
}

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

Tradeoff:

Databricks-specific tips

Databricks values this problem for two reasons: it tests whether you understand that pre-order (unlike in-order) uniquely encodes a tree without requiring a second traversal, and it surfaces serialization-format design instincts. Expect a system-design pivot: 'How would you serialize a 10-billion-node distributed tree?' The answer involves splitting at a depth threshold, hashing subtree roots into a key-value store, and stitching on read — the same approach used in Apache Spark's TreeAggregate. Touching on that extension separates staff-level answers from senior.

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

Practice these live with InterviewChamp.AI →