Skip to main content

297. Serialize and Deserialize Binary Tree

hardAsked at Airbnb

Encode a binary tree to a string and decode the string back. Airbnb asks this to test pre-order with explicit null markers vs level-order serialization — both work, but pick one and defend it.

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

Source citations

Public interview reports confirming this problem appears in Airbnb loops.

  • Glassdoor (2026-Q1)— Airbnb senior+ onsite reports list this as a recurring serialization hard.
  • Blind (2025-12)— Recurring in Airbnb backend interview reports.

Problem

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 in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. 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]

Example 2

Input
root = []
Output
[]

Approaches

1. Pre-order DFS with null markers (optimal)

Serialize: DFS pre-order, emit value or '#' for null. Deserialize: split into tokens and recursively consume.

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

Tradeoff: Recursive, easy to verify. Pre-order with null markers gives unique reconstruction even when values repeat.

2. Level-order BFS with null markers

Serialize: BFS, emit values left-to-right by level including nulls (with pruning of trailing nulls). Deserialize: split tokens, queue-build.

Time
O(n)
Space
O(n)
function serializeBFS(root) {
  if (!root) return '';
  const parts = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (!node) { parts.push('#'); continue; }
    parts.push(String(node.val));
    queue.push(node.left);
    queue.push(node.right);
  }
  while (parts.length && parts[parts.length - 1] === '#') parts.pop();
  return parts.join(',');
}
function deserializeBFS(data) {
  if (!data) return null;
  const tokens = data.split(',');
  const root = { val: parseInt(tokens[0], 10), left: null, right: null };
  const queue = [root];
  let i = 1;
  while (queue.length && i < tokens.length) {
    const node = queue.shift();
    if (i < tokens.length && tokens[i] !== '#') {
      node.left = { val: parseInt(tokens[i], 10), left: null, right: null };
      queue.push(node.left);
    }
    i++;
    if (i < tokens.length && tokens[i] !== '#') {
      node.right = { val: parseInt(tokens[i], 10), left: null, right: null };
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

Tradeoff: Matches the LeetCode visualizer format. Slightly more code than the pre-order version; pick whichever you can write bug-free.

Airbnb-specific tips

Airbnb wants you to defend your encoding choice. Say: 'I'll use pre-order with explicit nulls because the recursion-on-decode mirrors the recursion-on-encode — symmetric and easy to verify. Level-order matches the LeetCode visualizer but requires queue plumbing.' Either is correct; explicit nulls are required regardless.

Common mistakes

  • Skipping null markers — then 'left subtree of X' and 'right subtree of X' aren't separable in the output.
  • Using a comma as both delimiter and value (negative numbers OK if you parseInt; the comma boundary is safe).
  • Returning empty string '' for null roots but not handling it on deserialize.

Follow-up questions

An interviewer at Airbnb may pivot to one of these next:

  • Serialize a BST in fewer bytes (LC 449) — BST property allows post-order without nulls.
  • Serialize an N-ary tree (LC 428) — same idea, list children with explicit counts or delimiters.
  • Streaming serialization — output as nodes are visited; allows trees too large to fit in memory.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why explicit nulls?

Without them you can't tell whether a node has zero, one, or two children. The encoding wouldn't be invertible.

Pre-order or level-order — which does Airbnb prefer?

Both pass. Pre-order is cleaner to whiteboard; level-order matches the LC visualizer. Defend your choice with one sentence.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Serialize and Deserialize Binary Tree and other Airbnb interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →