Skip to main content

32. Serialize and Deserialize Binary Tree

hardAsked at Apple

Convert a binary tree to a string and back — Apple's UIKit view hierarchy and iCloud backup systems both serialize arbitrary tree structures to transmit state across devices; this hard problem tests whether you can design a stable, lossless encoding for hierarchical data.

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

Problem

Design an algorithm to serialize and deserialize a binary tree. Serialization is the process of converting a tree to a string; deserialization is converting the string back to the same tree structure. You may use any format — just ensure encode(decode(s)) == s and the tree structure is fully preserved.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -1000 <= Node.val <= 1000
  • Must handle null children explicitly in the encoding

Examples

Example 1

Input
root = [1,2,3,null,null,4,5]
Output
"1,2,N,N,3,4,N,N,5,N,N"

Explanation: Pre-order DFS with null markers; deserialization reconstructs exact structure

Example 2

Input
root = []
Output
""

Approaches

1. BFS level-order

Serialize with BFS queue, emitting 'N' for nulls. Deserialize by rebuilding level by level. Readable format but includes many trailing nulls on unbalanced trees.

Time
O(n)
Space
O(n)
function serialize(root) {
  if (!root) return '';
  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, node.right);
  }
  return res.join(',');
}

function deserialize(data) {
  if (!data) return null;
  const vals = data.split(',');
  const root = new TreeNode(+vals[0]);
  const queue = [root];
  let i = 1;
  while (queue.length && i < vals.length) {
    const node = queue.shift();
    if (vals[i] !== 'N') { node.left = new TreeNode(+vals[i]); queue.push(node.left); }
    i++;
    if (i < vals.length && vals[i] !== 'N') { node.right = new TreeNode(+vals[i]); queue.push(node.right); }
    i++;
  }
  return root;
}

Tradeoff:

2. Pre-order DFS (compact)

Serialize with recursive pre-order, emitting 'N' for nulls. Deserialize by consuming tokens from an iterator — cleaner recursion and more compact for deep trees.

Time
O(n)
Space
O(h)
function serialize(root) {
  const res = [];
  const dfs = (node) => {
    if (!node) { res.push('N'); return; }
    res.push(node.val);
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  return res.join(',');
}

function deserialize(data) {
  if (!data) return null;
  const vals = data.split(',');
  let idx = 0;
  const dfs = () => {
    if (vals[idx] === 'N') { idx++; return null; }
    const node = new TreeNode(+vals[idx++]);
    node.left = dfs();
    node.right = dfs();
    return node;
  };
  return dfs();
}

Tradeoff:

Apple-specific tips

Apple's UIKit encodes view hierarchies for Handoff, AirPlay mirroring, and iCloud state restoration — this problem tests exactly the serialization design judgment those engineers exercise daily. Apple interviewers will probe your format choice: why pre-order over in-order (in-order alone cannot uniquely reconstruct without shape info), why commas as delimiters (negative numbers contain minus signs, so no ambiguity), and whether your format is forward-compatible if the tree schema changes. Write the encode/decode pair together and test with an empty tree, a single node, and a tree with only left children — Apple's bar for edge-case rigor is high.

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

Practice these live with InterviewChamp.AI →