Skip to main content

24. Serialize and Deserialize Binary Tree

hardAsked at DigitalOcean

Encode and decode a binary tree to/from a string — a systems-thinking problem DigitalOcean uses to probe protocol design and state serialization.

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

Problem

Design an algorithm to serialize a binary tree to a single string and deserialize it back to the original tree structure. There is no restriction on your serialization format — you may choose any scheme that works correctly.

Constraints

  • Number of nodes in range [0, 10^4]
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [1,2,3,null,null,4,5]
Output
serialize then deserialize returns [1,2,3,null,null,4,5]

Example 2

Input
root = []
Output
[]

Approaches

1. Preorder with level-order JSON (naive)

Serialize to JSON array — correct but bulky and requires index arithmetic to reconstruct.

Time
O(n)
Space
O(n)
// Naive: JSON.stringify the tree object
// Problem: val/left/right nesting can be ambiguous for null children
// Prefer preorder with explicit null markers instead

Tradeoff:

2. Preorder DFS with null markers

Serialize with preorder traversal, using '#' for null nodes and ',' as delimiter. Deserialize by consuming tokens from a queue in the same preorder sequence.

Time
O(n)
Space
O(n)
const serialize = (root) => {
  const parts = [];
  function dfs(n) {
    if (!n) { parts.push('#'); return; }
    parts.push(n.val);
    dfs(n.left); dfs(n.right);
  }
  dfs(root);
  return parts.join(',');
};
const deserialize = (data) => {
  const tokens = data.split(',');
  let i = 0;
  function build() {
    if (tokens[i] === '#') { i++; return null; }
    const node = { val: +tokens[i++], left: null, right: null };
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
};

Tradeoff:

DigitalOcean-specific tips

DigitalOcean treats this as a protocol-design problem — discuss delimiter escaping, schema versioning, and backward compatibility as you would designing an RPC message format.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →