Skip to main content

100. Serialize and Deserialize Binary Tree

hardAsked at Snowflake

Convert a binary tree to and from a string. Snowflake asks this as the canonical tree-serialization problem — directly relevant to how their distributed scheduler ships compiled query plans across compute nodes.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake distributed-runtime team uses this for plan-shipping discussion.
  • Blind (2025-12)— Recurring at Snowflake SDE-II onsites.

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. Level-order BFS with nulls

BFS; emit values left-to-right per level, with explicit nulls.

Time
O(n)
Space
O(n)
// outline — works but null-bookkeeping is fiddly.

Tradeoff: Works but more error-prone.

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

serialize: pre-order DFS, emit 'null' for missing children. deserialize: split on comma, recursively consume tokens.

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

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

Tradeoff: Pre-order with null markers gives a unique reconstruction. The deserialize is a single pass with a global cursor.

Snowflake-specific tips

Snowflake interviewers want pre-order with nulls and the explanation that this representation uniquely determines the tree. Bonus signal: pivot to plan-shipping — Snowflake's distributed runtime ships compiled plans between compute nodes via a similar tree serialization, with the format encoded as Protocol Buffers or similar.

Common mistakes

  • Forgetting the null marker — without it, you can't tell where a subtree ends.
  • Using BFS without null markers — same problem.
  • Off-by-one with the global cursor in deserialize.

Follow-up questions

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

  • Serialize as BFS instead.
  • Serialize a binary search tree more compactly (no null markers needed — LC 449).
  • How does Snowflake serialize plans between compute nodes?

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 pre-order specifically?

Pre-order with null markers uniquely determines the tree. Inorder alone doesn't (multiple trees share an inorder). Pre-order + nulls is the simplest scheme that works.

How does this connect to plan shipping?

Snowflake's query plans are trees. The scheduler serializes them to bytes (Protocol Buffers), ships them to worker nodes, and deserializes them for execution. The pre-order + markers idea is the canonical version.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →