Problem Statement

Serialize and Deserialize Binary Tree

A binary tree is a shape where each box (we call it a node) holds a number and can point to up to two child boxes below it, a left one and a right one. The job here has two halves. First, serialize means turn the whole tree into one flat piece of text you can save to a file or send over the internet. Second, deserialize means take that text and rebuild the exact same tree from it. Think of it like flattening a paper model into a single string of instructions, then folding it back up so it looks identical to the original.

hardTreeTreesTime: O(n) · Space: O(n)

Signals to notice

convert tree to string and backpreserve structurehandle null children

Brute force first

No simpler alternative — serialization requires visiting every node. The question is format, not complexity. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Preorder traversal with null markers: serialize as 'val,left,right' where null children are marked with a sentinel (e.g., '#'). Deserialization reconstructs by reading values in the same preorder. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `root = [1,2,3,null,null,4,5]`

SERIALIZE: queue=[1], res=[]; pop 1 -> res=[1], enqueue 2,3 -> queue=[2,3]
pop 2 -> res=[1,2], enqueue null,null -> queue=[3,null,null]; pop 3 -> res=[1,2,3], enqueue 4,5 -> queue=[null,null,4,5]
pop null,null -> res=[1,2,3,null,null] -> queue=[4,5]; pop 4 -> res=[...,4] enqueue null,null; pop 5 -> res=[...,5] enqueue null,null
queue holds only nulls -> all appended; serialized = "1,2,3,null,null,4,5,null,null,null,null"
DESERIALIZE: vals=[1,2,3,null,null,4,5,null,null,null,null]; root=node(1), queue=[1], i=1
pop 1: vals[1]=2 -> left=2 push; i=2; vals[2]=3 -> right=3 push; i=3; queue=[2,3]
pop 2: vals[3]=null skip i=4; vals[4]=null skip i=5; pop 3: vals[5]=4 -> left=4 push i=6; vals[6]=5 -> right=5 push i=7; queue=[4,5]
pop 4: vals[7],vals[8]=null skip i=9; pop 5: vals[9],vals[10]=null skip i=11; queue empty
return reconstructed tree [1,2,3,null,null,4,5]

What must stay true

Preorder traversal with explicit null markers uniquely determines a binary tree. Every internal node has exactly two children (or null markers), so the structure is unambiguous. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

serialize(root):
  if not root: return "null"
  queue=[root]; res=[]
  while queue:
    node = queue.popleft()
    if node: res.add(node.val); queue.push(node.left); queue.push(node.right)
    else:    res.add(NULL)
  return join(res, ",")

deserialize(vals):           // vals = data.split(",")
  if vals[0]==NULL: return None
  root = node(vals[0]); queue=[root]; i=1
  while queue:
    node = queue.popleft()
    if vals[i]!=NULL: node.left  = node(vals[i]); queue.push(node.left)
    i++                        // increment ALWAYS, even when null
    if vals[i]!=NULL: node.right = node(vals[i]); queue.push(node.right)
    i++                        // increment ALWAYS, even when null
  return root

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not serializing null children — without null markers, you can't distinguish between a node with only a left child and one with only a right child. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Trees Pattern