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 Sam K., 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.

More Airbnb coding interview questions

See all Airbnb problems →

Companies that also ask Serialize and Deserialize Binary Tree