Skip to main content

24. Serialize and Deserialize Binary Tree

hardAsked at Chime

Design serialize() and deserialize() functions that round-trip an arbitrary binary tree through a string.

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

Problem

Serialization is the process of converting a data structure into a sequence of bits so that it can be stored or transmitted, and reconstructed later. Design serialize() and deserialize() such that serialize then deserialize returns an identical binary tree.

Constraints

  • 0 <= number of nodes <= 10^4
  • -1000 <= Node.val <= 1000

Examples

Example 1

Input
root = [1,2,3,null,null,4,5]
Output
round-trip equals original

Example 2

Input
root = []
Output
round-trip equals null

Approaches

1. Level-order with placeholders

BFS the tree emitting values level by level, using a sentinel for null children. Deserialize by walking the BFS string and attaching children to a queue of parents.

Time
O(n)
Space
O(n)
// serialize: bfs, push 'null' for missing
// deserialize: split, walk queue of parents

Tradeoff:

2. Pre-order DFS with sentinels

Use a pre-order traversal emitting either node.val or a # sentinel for null, joined by commas. Deserialize by consuming tokens in pre-order using a queue/index.

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

Tradeoff:

Chime-specific tips

Chime serializes neobank ledger snapshots for replay, so explain how pre-order traversal keeps the on-disk format compact and stable across schema bumps.

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 Chime interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →