Skip to main content

23. Serialize and Deserialize Binary Tree

hardAsked at JetBrains

Encode a binary tree to a string and decode it back losslessly — JetBrains uses this to test tree-serialization design, mirroring how PSI stubs hit disk and rehydrate.

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

Problem

Design serialize and deserialize methods for a binary tree such that any tree of integers can be encoded to a string and reconstructed identically. The format is open as long as it round-trips.

Constraints

  • 0 <= 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] (round-trips)

Example 2

Input
root=[]
Output
[] (round-trips)

Approaches

1. Inorder-only serialization

Emit inorder traversal as a flat string; loses shape information and can't reconstruct the tree.

Time
O(n)
Space
O(n)
// only inorder is ambiguous: many distinct trees share the same inorder traversal

Tradeoff:

2. Preorder with explicit null markers

Preorder DFS, writing 'null' for missing children. Deserialization reads tokens in order and reconstructs via recursion. Same shape JetBrains stub indices use to persist parsed declarations.

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

Tradeoff:

JetBrains-specific tips

JetBrains expects you to call out why preorder + null sentinels round-trips while inorder alone doesn't — the same invariant their stub-index format relies on to rebuild PSI declarations without re-parsing source.

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

Practice these live with InterviewChamp.AI →