Skip to main content

21. Serialize and Deserialize Binary Tree

hardAsked at GitHub

Design a codec to convert a binary tree to/from a string, mirroring how GitHub serializes ASTs and repository tree structures for storage and wire transfer.

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

Problem

Design a class Codec with a serialize(root) method that encodes a binary tree to a string and a deserialize(data) method that decodes the string back to the original tree structure.

Constraints

  • The number of nodes 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 then deserialize returns original tree

Example 2

Input
root = []
Output
deserialize(serialize(null)) = null

Approaches

1. In-order + pre-order pair (flawed for duplicates)

Store two traversal arrays and reconstruct — fails when duplicate values exist.

Time
O(n)
Space
O(n)
// Store inorder+preorder arrays
// Problem: duplicate node values make reconstruction ambiguous

Tradeoff:

2. BFS level-order with null markers

Serialize using BFS, encoding null children as 'N'. Deserialize by BFS-rebuilding the queue: pop a node, read next two tokens, create real children or nulls, push real children to queue.

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

Tradeoff:

GitHub-specific tips

GitHub system-design questions often pivot from this into: 'How would you serialize a DAG (commit graph) rather than a tree?' — be ready to explain topological ordering and cycle detection for DAG serialization.

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

Practice these live with InterviewChamp.AI →