Serialize and Deserialize Binary Tree — BFS Queue Encoding

Problem Statement

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

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

Input:  root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]   // round-trip

Input:  root = []
Output: []

Why This Problem Matters

LeetCode 297 Serialize and Deserialize Binary Tree is a flagship FAANG design question and shows up at Amazon, Google, Meta, Microsoft, and Apple. It tests three competencies at once: choosing the right traversal (BFS or pre-order), handling null sentinels correctly, and parsing the encoded string back into a tree. Both BFS-with-queue and DFS-with-recursion are accepted; recruiters often watch which one the candidate picks and why.

This problem is also a litmus test for production thinking. A junior candidate writes a solution that round-trips. A senior candidate also discusses encoding format choices (delimiter handling, null tokens, large value ranges, schema versioning) and the trade-offs between BFS-flat encoding and DFS-with-parentheses encoding.

The Core Insight

Use BFS to produce a level-order encoding. The queue gives us nodes in layer-by-layer order; we emit each node's value (or "null" for missing children) into a comma-separated string. Deserialization parses the tokens, builds the root, and uses another queue to attach left and right children layer by layer.

Why BFS over DFS? The BFS encoding mirrors the LeetCode array convention exactly, makes nulls explicit, and requires no recursion (which can stack-overflow on skewed trees with thousands of nodes). DFS with pre-order plus null sentinels also works, but BFS is the most common production format.

Encoding rules:

Empty tree: "".
Otherwise comma-separated values where each non-null node emits two children (each "null" or a value).

Visual Dry Run

Tree:

Serialization (BFS):

Queue starts: [1]. Emit "1". Push 1's children: 2, 3.
Queue [2, 3]. Pop 2; emit "2". Push 2's children: null, null.
Pop 3; emit "3". Push 3's children: 4, 5.
Queue [null, null, 4, 5]. Pop null; emit "null".
Pop null; emit "null".
Pop 4; emit "4". Push null, null.
Pop 5; emit "5". Push null, null.
Queue holds six nulls. Emit "null" six times.

Result: "1,2,3,null,null,4,5,null,null,null,null,null,null".

Optimization: stop emitting trailing nulls. The deserializer can treat missing tokens as null.

Deserialization:

Read tokens: ["1","2","3","null","null","4","5"].
Build root from "1". Queue [root].
Pop root. Next two tokens "2", "3" become left and right of root. Queue [node2, node3].
Pop node2. Next two tokens "null", "null"; nothing attached. Queue [node3].
Pop node3. Next two tokens "4", "5" become left and right of node3. Queue [node4, node5].
Pop node4. No more tokens (or "null", "null").
Pop node5. No more tokens.

Tree round-trips correctly.

Solution (Optimal)

from collections import deque
from typing import Optional, List
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        if not root:
            return ""
        out: List[str] = []
        q = deque([root])
        while q:
            node = q.popleft()
            if node is None:
                out.append("null")
            else:
                out.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
        return ",".join(out)
 
    def deserialize(self, data: str) -> Optional[TreeNode]:
        if not data:
            return None
        tokens = data.split(",")
        root = TreeNode(int(tokens[0]))
        q = deque([root])
        i = 1
        while q and i < len(tokens):
            node = q.popleft()
            if i < len(tokens) and tokens[i] != "null":
                node.left = TreeNode(int(tokens[i]))
                q.append(node.left)
            i += 1
            if i < len(tokens) and tokens[i] != "null":
                node.right = TreeNode(int(tokens[i]))
                q.append(node.right)
            i += 1
        return root

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
 
const serialize = function (root) {
  if (!root) return "";
  const out = [];
  const q = [root];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    if (node === null) {
      out.push("null");
    } else {
      out.push(String(node.val));
      q.push(node.left);
      q.push(node.right);
    }
  }
  return out.join(",");
};
 
const deserialize = function (data) {
  if (!data) return null;
  const tokens = data.split(",");
  const root = new TreeNode(Number(tokens[0]));
  const q = [root];
  let head = 0, i = 1;
  while (head < q.length && i < tokens.length) {
    const node = q[head++];
    if (i < tokens.length && tokens[i] !== "null") {
      node.left = new TreeNode(Number(tokens[i]));
      q.push(node.left);
    }
    i++;
    if (i < tokens.length && tokens[i] !== "null") {
      node.right = new TreeNode(Number(tokens[i]));
      q.push(node.right);
    }
    i++;
  }
  return root;
};

Complexity. Both serialize and deserialize are O(n) time and O(n) space.

Common Mistakes

Using DFS pre-order without null sentinels. Pre-order alone does not uniquely determine the tree — you need either null sentinels or post-order plus pre-order.
Forgetting to handle empty trees. The empty string is the standard representation.
Pushing real nulls into the queue but not emitting them. Either drop nulls and emit "null" inline (cleaner) or push and check.
Using JSON.stringify or Python repr for values without escaping commas. Use a fixed delimiter and integer values.
Recursing on deeply skewed trees and overflowing the stack. BFS with an explicit queue avoids this.

Interview Tips

Pick BFS over DFS for two reasons: matches LeetCode array convention, no recursion stack risk on skewed trees.
Discuss alternative encodings: pre-order with nulls (DFS), post-order, or schema-driven binary formats. Recruiters expect awareness of trade-offs.
Handle edge cases (empty tree, single node, deeply skewed) early in the interview.
Mention production concerns: schema versioning (prepend a version byte), large value ranges (varint encoding), null compaction (drop trailing nulls).
Mention that this problem also tests your queue manipulation skills — show the deque clearly.

Follow-up Questions

What if values can include commas? Use length-prefix framing or escape commas in values.
How would you serialize a generic n-ary tree? Emit children count after each value or use parentheses.
What if the tree is very deep (10^6 nodes)? BFS handles it gracefully; DFS might overflow recursion.
Compress the output? Run-length encode trailing nulls, or use Huffman coding for values.
What about thread-safe serialization? Snapshot the tree (or freeze updates) before serializing.

Key Takeaways

BFS with a queue produces a clean level-order encoding that mirrors LeetCode's array convention.
Use explicit "null" tokens for missing children to make decoding unambiguous.
Trailing nulls can be omitted; the decoder treats missing tokens as null.
BFS deserialization uses a parallel queue to attach children in lockstep.
Time and space are both O(n); avoid recursion to prevent stack overflow on skewed trees.
This pattern generalizes to n-ary trees, graphs (with cycle detection), and arbitrary nested structures.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal)#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading