Serialize and Deserialize a Binary Tree: Two Approaches That Actually Work

Serialization is one of those problems where the difficulty isn't the algorithm — it's the design decision. There are multiple valid approaches, and the choice reveals how you think about trade-offs.

The core problem (LeetCode 297): given a binary tree, convert it to a string (serialize) and convert that string back to the original tree (deserialize). No restrictions on format — just make it round-trip correctly.

This is a Hard on LeetCode, but once you understand why certain traversal orders work and others don't, the implementation is straightforward.

Why Not Just Store the Values?

You might think: "Store the node values in an array, reconstruct from that." The problem is ambiguity.

These two trees both produce an in-order traversal of [1, 2, 3]:

    2           1
   / \           \
  1   3           2
                   \
                    3

In-order alone is not enough to reconstruct a tree uniquely. You need either:

1. Two traversals (like in-order + pre-order), or
2. One traversal with explicit null markers

Approach 2 is what almost every correct serialization uses: encode null nodes explicitly.

Approach 1: Preorder DFS with Null Markers

Preorder visits a node before its subtrees. With null markers ("N"), the serialized string uniquely encodes the tree's structure.

The key insight: during deserialization, when you encounter a non-null value, you know the next values in the string will describe its left subtree fully before its right subtree. You can reconstruct the tree by walking the string exactly as preorder produces it.

This tree serializes to: "1,2,N,4,N,N,3,N,N".

Reading that back:

• 1 → create node 1, recurse left
• 2 → create node 2, recurse left
• N → null, return
• 4 → create node 4, recurse left
• N → null, return
• N → null, return (node 4's right)
• return (node 2's right — which is node 4, now complete)
• 3 → create node 3, recurse left
• N → null
• N → null
• return (node 3 complete)
• return (tree complete)

// Time: O(n) for both  Space: O(n) for output string + O(h) call stack for DFS
const serialize = (root) => {
  const parts = [];
 
  const dfs = (node) => {
    if (!node) {
      parts.push('N');
      return;
    }
    parts.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  };
 
  dfs(root);
  return parts.join(',');
};
 
const deserialize = (data) => {
  const vals = data.split(',');
  let i = 0; // shared index across recursive calls
 
  const build = () => {
    if (vals[i] === 'N') {
      i++;
      return null;
    }
    const node = { val: parseInt(vals[i++]), left: null, right: null };
    node.left = build();
    node.right = build();
    return node;
  };
 
  return build();
};

The i counter is the subtle part. It advances through the array across recursive calls — each call to build() consumes exactly as many tokens as the subtree it represents. This is the preorder guarantee: the left subtree's tokens come before the right subtree's tokens, so the index advances correctly.

Alternatively: Use a Queue Instead of an Index

Some people find this cleaner — pass a queue of tokens instead of an index:

// Time: O(n)  Space: O(n)
const deserializeQueue = (data) => {
  const queue = data.split(',');
 
  const build = () => {
    const val = queue.shift();
    if (val === 'N') return null;
    const node = { val: parseInt(val), left: null, right: null };
    node.left = build();
    node.right = build();
    return node;
  };
 
  return build();
};

queue.shift() is O(n) for an array, but for interviews this is fine. Mention that a real implementation would use an iterator or index pointer to avoid the O(n²) worst case.

Approach 2: BFS / Level-Order

Instead of DFS, use level-order traversal. Serialize row by row. Null nodes are encoded explicitly, and you stop adding children of null nodes.

    1
   / \
  2   3
   \
    4
 
Serializes to: "1,2,3,N,4,N,N,N,N"

Note the trailing markers. This version enqueues the children of every real node, including leaves, so each leaf contributes two Ns of its own. That is more verbose than it needs to be — the deserializer below stops as soon as the queue drains, so trailing nulls could be trimmed before returning. Leaving them in keeps the two halves symmetric, which is easier to get right under interview pressure.

// Time: O(n)  Space: O(n)
// The `head` pointer is what makes the O(n) true — see the note below.
const serializeBFS = (root) => {
  if (!root) return '';
  const parts = [];
  const queue = [root];
  let head = 0;
 
  while (head < queue.length) {
    const node = queue[head++];
    if (!node) {
      parts.push('N');
      continue;
    }
    parts.push(String(node.val));
    queue.push(node.left);
    queue.push(node.right);
  }
 
  return parts.join(',');
};
 
const deserializeBFS = (data) => {
  if (!data) return null;
  const vals = data.split(',');
  const root = { val: parseInt(vals[0]), left: null, right: null };
  const queue = [root];
  let head = 0; // queue cursor
  let i = 1;    // token cursor
 
  while (head < queue.length && i < vals.length) {
    const node = queue[head++];
 
    // Left child
    if (vals[i] !== 'N') {
      node.left = { val: parseInt(vals[i]), left: null, right: null };
      queue.push(node.left);
    }
    i++;
 
    // Right child
    if (i < vals.length && vals[i] !== 'N') {
      node.right = { val: parseInt(vals[i]), left: null, right: null };
      queue.push(node.right);
    }
    i++;
  }
 
  return root;
};

The BFS deserialization mirrors the BFS serialization: for each node we advance past, the next two tokens in the array are its left and right children. Non-null children get pushed onto the queue to be processed later.

Both functions use a head index rather than queue.shift(), for the same reason flagged for deserializeQueue above and deserializeBST below — and here it matters more, because the BFS queue holds up to O(n) nodes rather than a handful. shift() re-indexes the whole array on every call, so an O(n) annotation over a shift()-driven BFS loop is simply not true. On complete binary trees, best of several runs on Node 22:

About 4× per doubling on the shift() side against 2× on the pointer side: quadratic versus linear. (The first deserializeBFS step jumps by more than 4×, because at 20,000 the queue is still small enough that V8's shift() fast path helps; from 40,000 on it settles into the 4× pattern. serializeBFS is worse throughout because its queue holds every null too, so it's about twice as long for the same tree.) Output is byte-identical either way — the pointer just leaves the consumed prefix in place instead of paying to delete it, which costs nothing here because the queue is already O(n) live.

DFS vs BFS — which to use?

Either works. DFS (preorder) tends to be slightly simpler to implement and is the more common interview answer. BFS is fine too but the index bookkeeping for deserialization is a bit more manual. Pick one and know it cold.

Variant: Serialize and Deserialize BST (LeetCode 449)

If the tree is a BST (not just any binary tree), you can do better.

For a BST, in-order traversal is always sorted. But more useful here: preorder traversal alone (without null markers) uniquely identifies a BST. Here's why: if you have the preorder sequence, you know the root (first element) and you can determine the left/right split by BST property — everything less than root goes left, everything greater goes right.

// Time: O(n) serialize, O(n) reconstruct  Space: O(n)
// (build() is called exactly 2n+1 times — once per node plus once per null slot)
// Caveat: vals.shift() below is O(n) on a JS array, which makes this listing O(n^2)
// in practice. Swap in an index cursor, as in the preorder version above, to get real O(n).
const serializeBST = (root) => {
  const vals = [];
  const preorder = (node) => {
    if (!node) return;
    vals.push(node.val);
    preorder(node.left);
    preorder(node.right);
  };
  preorder(root);
  return vals.join(',');
};
 
const deserializeBST = (data) => {
  if (!data) return null;
  const vals = data.split(',').map(Number);
 
  const build = (low, high) => {
    if (!vals.length || vals[0] < low || vals[0] > high) return null;
    const val = vals.shift();
    const node = { val, left: null, right: null };
    node.left = build(low, val);
    node.right = build(val, high);
    return node;
  };
 
  return build(-Infinity, Infinity);
};

The build(low, high) approach is the same bounds-check technique from BST validation — it uses the BST invariant to know when the current value belongs to the left or right subtree without explicit null markers.

Comparing the Approaches

For LeetCode 297, use DFS preorder with null markers. For 449, use preorder without markers plus the bounds check.

Interview Tips

Start by asking what kind of tree. "Is this a general binary tree or a BST?" This immediately shows you know the distinction and the different techniques available.

Explain before you code. The hardest part of these problems is the design, not the implementation. Say: "I'll use preorder DFS with null markers for the serialize side. For deserialize, I'll use a shared index that advances as the recursion consumes tokens." If the interviewer follows along, you've already demonstrated the core understanding.

The shared state in deserialization (the index or queue) is where most people trip up under pressure. Make this explicit: "The i variable is shared across all recursive calls — it's like a cursor walking through the token array as the recursion mirrors the original tree traversal."

Edge cases worth mentioning:

• Empty tree: serialize(null) should return some sentinel ("" or "N") and deserialize handles it

• Single node: works without special-casing if your null markers are correct

• Very deep trees: DFS has call stack depth equal to tree height. For a degenerate (linked-list-shaped) tree, this could be O(n) depth. BFS avoids this.

• A node whose value collides with the null marker. LeetCode's 297 constrains values to integers, so 'N' is safe there, but the moment you reuse this on real data it isn't. serialize does String(node.val), so a node whose value is the string 'N' emits the token N — indistinguishable from a null. Round-trip a three-node tree with 'N' at the root and the whole tree disappears:

  const leaf = (val) => ({ val, left: null, right: null });
  const t = { val: 'N', left: leaf(1), right: leaf(2) };
   
  serialize(t);                // "N,1,N,N,2,N,N"
  deserialize(serialize(t));   // null   ← the entire tree, gone silently

  With 'N' further down it's worse than losing the tree, because you get a plausible tree that's the wrong shape — {1, left: {'N', left: 7}, right: 3} serialises to "1,N,7,N,N,N,3,N,N" and comes back as {1, left: null, right: {7}}. Node 3 is gone, node 7 has moved, no error anywhere. Same class of bug: a value containing the , separator ({ val: '1,2' }) splits into two tokens and desynchronises the cursor, which crashes with a RangeError. The fixes are the usual ones — pick a sentinel outside the value domain, length-prefix or quote each token, or just use JSON.stringify on the token array. Worth saying out loud: "I'm assuming values can't collide with my marker; if they can, I'd escape them."

  🚨

  This is the reason "just use 'N' for null" is a problem-specific choice, not a general one. If an interviewer asks "what if values are arbitrary strings?", the answer is that a marker drawn from the same alphabet as the data is not a marker.

LeetCode 449 follow-up. Interviewers who give you 297 sometimes follow up with "what if I told you it's a BST?" The answer: you can drop the null markers because preorder + BST property gives unique reconstruction. Knowing this distinction is the sign of someone who understands why different serializations work.

The deeper thing to internalize: serialization is about uniqueness. Any traversal that uniquely encodes a tree structure is a valid serialization. Preorder with null markers works for any binary tree. Preorder without markers works for BSTs because the BST invariant provides the missing structural information. Two traversals without null markers (preorder + inorder) also work but are more complex to implement and rarely asked.