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

More Datadog coding interview questions

See all Datadog problems →

Companies that also ask Serialize and Deserialize Binary Tree