Skip to main content

87. Serialize and Deserialize Binary Tree

hardAsked at Datadog

Design serialize and deserialize for an arbitrary binary tree. Datadog uses this as the canonical wire-format question — same shape as their distributed metric-tree snapshot format that flows between ingest and query nodes.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — direct wire-format analog.
  • Blind (2025-11)— Recurring at Datadog.

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.

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. BFS with null markers

Level-order with explicit nulls. Same shape as LeetCode's input format.

Time
O(n)
Space
O(n)
// BFS; for each node, emit val (or 'N'); on deserialize, BFS rebuild with index tracking.

Tradeoff: Verbose. Datadog accepts; preorder is cleaner.

2. Preorder DFS with null markers (optimal)

Preorder traversal emits val,val,...,N,N,... — split on comma. Deserialize via shared index pointer.

Time
O(n)
Space
O(n)
function serialize(root) {
  const parts = [];
  function dfs(node) {
    if (!node) { parts.push('N'); return; }
    parts.push(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 (tokens[i] === 'N') { 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: Clean and minimal. The 'N' marker disambiguates null vs missing. Datadog-canonical.

Datadog-specific tips

Datadog grades on the null-marker approach — without it, you can't reconstruct the tree structure from values alone. Articulate why preorder + null markers is uniquely decodable.

Common mistakes

  • Trying to serialize without null markers — ambiguous (different trees produce same output).
  • Using JSON.stringify on objects with cycles — would crash on, say, parent pointers if added.
  • Forgetting to advance the index during deserialize — infinite loop.

Follow-up questions

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

  • Serialize/Deserialize BST (LC 449) — no null markers needed.
  • Serialize/Deserialize N-ary Tree (LC 428).
  • Datadog-style: wire format for distributed metric-tree snapshots.

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 null markers?

Without them, tree shape is ambiguous: [1,2] could be either {1, left:2} or {1, right:2}.

BFS or DFS serialization?

Both work. DFS (preorder) is simpler to deserialize via recursion. BFS matches LeetCode's input format.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →