Skip to main content

297. Serialize and Deserialize Binary Tree

hardAsked at Google

Encode a binary tree to a string and decode it back. Google asks this to test whether you handle null markers correctly and choose a traversal order that both serialize and deserialize can agree on without ambiguity.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4/L5 onsite reports cite this as the tree-design round.
  • Blind (2025-09)— Recurring Google interview problem for senior IC roles.

Problem

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Constraints

  • The number of nodes in the tree is in the range [0, 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 BFS with null markers

Serialize by BFS, emitting 'null' for missing children. Deserialize by reading the array and rebuilding level-by-level.

Time
O(n)
Space
O(n)
function serializeBFS(root) {
  if (!root) return '[]';
  const out = [];
  const q = [root];
  while (q.length) {
    const node = q.shift();
    if (!node) { out.push('null'); continue; }
    out.push(String(node.val));
    q.push(node.left);
    q.push(node.right);
  }
  return '[' + out.join(',') + ']';
}

function deserializeBFS(data) {
  if (data === '[]') return null;
  const vals = data.slice(1, -1).split(',');
  const root = { val: Number(vals[0]), left: null, right: null };
  const q = [root];
  let i = 1;
  while (q.length && i < vals.length) {
    const node = q.shift();
    if (vals[i] !== 'null') {
      node.left = { val: Number(vals[i]), left: null, right: null };
      q.push(node.left);
    }
    i++;
    if (i < vals.length && vals[i] !== 'null') {
      node.right = { val: Number(vals[i]), left: null, right: null };
      q.push(node.right);
    }
    i++;
  }
  return root;
}

Tradeoff: Matches LeetCode's serialization format and is recognizable to anyone who's seen tree inputs. Slightly verbose due to the dual queue/index bookkeeping.

2. Preorder DFS with null markers (optimal for whiteboard)

Serialize via preorder, emit '#' for null. Deserialize by reading tokens in order and recursing.

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

function deserialize(data) {
  const tokens = data.split(',');
  let i = 0;
  function build() {
    if (i >= tokens.length) return null;
    const t = tokens[i++];
    if (t === '#') return null;
    return { val: Number(t), left: build(), right: build() };
  }
  return build();
}

Tradeoff: Cleaner to whiteboard. Preorder + null markers fully encodes the structure because at each node you know exactly when to consume the left vs right subtree.

Google-specific tips

Google interviewers grade this on whether you explain WHY preorder + null markers is sufficient: each node's serialization includes its own value plus two complete subtree serializations, so the structure is unambiguous on the way back up. Skipping the null markers (e.g. just emitting values) is the classic trap because then you can't distinguish a left-only subtree from a right-only one.

Common mistakes

  • Forgetting null markers — without them, structure is ambiguous.
  • Using inorder instead of preorder — inorder alone doesn't uniquely determine a binary tree.
  • Using shared mutable index across recursive calls without proper scoping.

Follow-up questions

An interviewer at Google may pivot to one of these next:

  • Serialize and Deserialize BST (LC 449) — can skip null markers because BST property reconstructs structure.
  • Serialize and Deserialize N-ary Tree (LC 428) — needs a children-count marker.
  • What if the tree has parent pointers?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why preorder and not inorder?

Inorder alone doesn't uniquely determine a binary tree — [1,2,3] could be many shapes. Preorder + null markers does.

BFS or DFS — which does Google prefer?

Both score the same. DFS is shorter to whiteboard; BFS matches the typical LeetCode visualization. Pick whichever you can code without bugs.

Practice these live with InterviewChamp.AI

Drill Serialize and Deserialize Binary Tree and other Google interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →