Skip to main content

31. Serialize and Deserialize Binary Tree

hardAsked at Postman

Encode a binary tree to a string and decode it back to an identical tree.

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

Problem

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how the algorithm should work; you just need to ensure that a binary tree can be serialized to a string and that string can be deserialized to the original 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
[1,2,3,null,null,4,5]

Example 2

Input
root = []
Output
[]

Approaches

1. Level-order with nulls

BFS the tree, emitting null markers. Deserialize by reading values and queuing parents to attach children.

Time
O(n)
Space
O(n)
// BFS queue: emit val or 'null'; on deserialize, queue parent, read two children from tokens

Tradeoff:

2. Pre-order DFS with sentinel

Serialize via pre-order, writing 'N' for null. Deserialize by consuming tokens in pre-order using a generator.

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

Tradeoff:

Postman-specific tips

Postman serializes their Collection trees to JSON for sync — they expect you to call out trade-offs (pre-order DFS is compact and stream-friendly; BFS is easier to debug visually).

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

Practice these live with InterviewChamp.AI →