Skip to main content

26. Serialize and Deserialize Binary Tree

hardAsked at ServiceNow

Design algorithms to convert a binary tree to a string and back without information loss. ServiceNow asks this hard problem because serializing and restoring hierarchical data structures is core to their workflow-snapshot and CMDB-export features — interviewers grade candidates on null-marker strategy and delimiter robustness.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Blind (2026)— Reported as a ServiceNow Staff/Senior SDE hard coding question.
  • LeetCode Discuss (2025)— Flagged as a ServiceNow design-adjacent hard problem for senior loops.

Problem

Design an algorithm to serialize a binary tree to a string and deserialize a string back to a binary tree. The encoded string should faithfully represent the structure of the tree, including null nodes, and must support arbitrary integer values at each node.

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
Serialize to '1,2,null,null,3,4,null,null,5,null,null' and deserialize back to the original tree.

Explanation: Pre-order DFS with null markers uniquely encodes the tree structure.

Approaches

1. BFS level-order encoding

Encode node values level by level (including nulls), decode by reading level by level and assigning left/right children from a queue.

Time
O(n)
Space
O(n)
// Serialize
function serialize(root) {
  if (!root) return '';
  const q = [root], res = [];
  while (q.length) {
    const node = q.shift();
    if (!node) { res.push('null'); continue; }
    res.push(node.val);
    q.push(node.left, node.right);
  }
  return res.join(',');
}
// Deserialize
function deserialize(data) {
  if (!data) return null;
  const vals = data.split(',');
  const root = new TreeNode(+vals[0]);
  const q = [root]; let i = 1;
  while (q.length) {
    const node = q.shift();
    if (vals[i] !== 'null') { node.left = new TreeNode(+vals[i]); q.push(node.left); }
    i++;
    if (vals[i] !== 'null') { node.right = new TreeNode(+vals[i]); q.push(node.right); }
    i++;
  }
  return root;
}

Tradeoff: Produces a more compact string for wide trees, but level-order null expansion can still be large for degenerate trees. Slighly more code than the DFS version.

2. Pre-order DFS with null markers

Serialize by DFS pre-order, writing 'null' for absent nodes. Deserialize by consuming values from a split array using an index pointer — pre-order uniquely determines the tree structure because the root is always first, followed by the full left subtree, then the right subtree.

Time
O(n)
Space
O(n)
function serialize(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(',');
}

function deserialize(data) {
  const vals = data.split(',');
  let idx = 0;
  function build() {
    if (vals[idx] === 'null') { idx++; return null; }
    const node = new TreeNode(Number(vals[idx++]));
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

Tradeoff: Minimal, elegant, and O(n). Using a closure over idx (or a pointer object) avoids global state. Interviewers value this version because it demonstrates mastery of recursive structure — the tree literally encodes and decodes itself.

ServiceNow-specific tips

ServiceNow interviewers grade this problem on three axes: correct null handling (tree structure is lost without null markers), delimiter robustness (comma works when values are integers; discuss escaping if values could contain the delimiter), and the recursive self-similarity insight (pre-order uniquely determines the tree). Mention that ServiceNow's workflow export uses a similar DFS serialization for nested activity nodes.

Common mistakes

  • Omitting null markers — makes it impossible to distinguish a node with one child from a node with two children or a leaf.
  • Using a global variable for the deserialize index instead of a closure — causes bugs when the function is called concurrently.
  • Parsing vals[i] with parseInt instead of Number — parseInt stops at the first non-digit, silently truncating negative numbers.

Follow-up questions

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

  • Serialize and deserialize an N-ary tree.
  • Serialize and deserialize a BST — can omit null markers because structure is implied by value ordering (LC 449).
  • Design a compact binary format instead of a comma-separated string (protocol buffer approach).

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 does pre-order work but in-order doesn't?

In-order traversal of a binary tree (without null markers) does not uniquely determine the tree — multiple different trees can produce the same in-order sequence. Pre-order with null markers is unique because the root is always first, and the null markers delimit subtree boundaries precisely.

What if node values can contain the comma delimiter?

Use a length-prefixed encoding (e.g., '5:hello') or URL-encode the values. For integer-only trees, commas are safe. At ServiceNow, IDs are integers so this is not a real concern, but mentioning it signals production-awareness.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →