Trees crash course ↗ · 137

297. Serialize and Deserialize Binary Tree

Encode any binary tree to a string and decode it back to the exact same tree. A preorder DFS that emits a sentinel # for every null child makes the shape self-describing — so reading the tokens back front-to-back rebuilds it in one pass.

● HardDFSPreorderTypeScript

PROBLEM What we're solving

Design serialize(root) (tree → string) and deserialize(data) (string → tree) so that deserialize(serialize(t)) reproduces t exactly. For the tree 1,2,3,null,null,4,5 (root 1; left 2; right 3 with children 4 and 5), a preorder encoding is 1,2,#,#,3,4,#,#,5,#,#, which must decode back to the same tree.

KEY IDEA Null markers make a traversal reversible

Insight → a bare preorder list of values is ambiguous— you can't tell where a subtree ends. Emit a sentinel (#) for every missing child and the stream becomes a complete, self-describing blueprint. Decoding is then a mirror of encoding: the same recursion consumes one token per call, in the same order, so the recursion stack reconstructs identical structure.

RECIPE Emit value + nulls, then replay the recursion

1 · Serialize (preorder). For a real node, append its value, then recurse left, then right — value before children so the root is the first token.
2 · Mark the holes. For a null node, append # and stop. These markers are what make the shape recoverable.
3 · Deserialize (same order). Keep a single cursor i. Read one token: if #, this child is null; else create the node, then build its left subtree, then its right — consuming tokens in the exact order serialize produced them.
4 · Trust the cursor. Because each recursive call eats exactly one token before descending, the front-to-back stream lines up perfectly with the rebuild — no index math needed.

Classic confusion → you must emit # for nulls. Without them, 1,2 could be "2 is the left child" or"2 is the right child" — undecidable. A preorder traversal that records nulls is reversible; one that skips them is not.

COST Complexity & alternatives

Search-on-decode (no markers)

O(n²)

Ambiguous; needs scans/heuristics to find subtree splits.

Preorder + null sentinels

O(n)

One pass each way; O(n) string, O(h) recursion stack.

Where the time goes

Serialize visits each of n real nodes plus the n+1 null slots exactly once → O(n). Deserialize consumes each token once → O(n). Space is O(n) for the string and O(h) for the recursion stack (h = height; O(n) worst case for a skewed tree).

Pattern transfer →the "traversal + null markers" trick also encodes BSTs (where you can even drop the markers and use value bounds), powers Construct Tree from Preorder & Inorder, and underlies Find Duplicate Subtrees(the serialization string is the subtree's identity).

RUN IT Preorder out, preorder back in

tree =

step 0 / 25

STARTSerialize. Walk the tree in preorder(node → left → right), appending each value to the output. A # marks a missing child so the shape is recoverable.

1class TreeNode {
2  val: number;
3  left: TreeNode | null;
4  right: TreeNode | null;
5  constructor(val: number) {
6    this.val = val;
7    this.left = null;
8    this.right = null;
9  }
10}
11 
12const NULL = '#';
13 
14// Preorder DFS: node, then left, then right. '#' marks an absent child.
15▶function serialize(root: TreeNode | null): string {
16▶  const out: string[] = [];
17▶  const dfs = (node: TreeNode | null): void => {
18    if (node === null) {
19      out.push(NULL);          // record the hole so shape survives
20      return;
21    }
22    out.push(String(node.val)); // emit value BEFORE descending (preorder)
23    dfs(node.left);
24    dfs(node.right);
25  };
26  dfs(root);
27  return out.join(',');
28}
29 
30// Rebuild by consuming the same preorder stream front-to-back.
31function deserialize(data: string): TreeNode | null {
32  const tokens = data.split(',');
33  let i = 0;
34  const build = (): TreeNode | null => {
35    const token = tokens[i++];   // consume one token, advance
36    if (token === NULL) return null;
37    const node = new TreeNode(Number(token));
38    node.left = build();         // left subtree consumes next tokens
39    node.right = build();        // right subtree consumes what remains
40    return node;
41  };
42  return build();
43}

State

serialize

phase

[]

out

—

node

emitting (serialize)consuming (deserialize)real node value / out array# / nulltokens array / past

slowfast

TYPESCRIPT The solution, annotated

serializeTree.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const NULL = '#';

// Preorder DFS: node, then left, then right. '#' marks an absent child.
function serialize(root: TreeNode | null): string {
  const out: string[] = [];
  const dfs = (node: TreeNode | null): void => {
    if (node === null) {
      out.push(NULL);          // record the hole so shape survives
      return;
    }
    out.push(String(node.val)); // emit value BEFORE descending (preorder)
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  return out.join(',');
}

// Rebuild by consuming the same preorder stream front-to-back.
function deserialize(data: string): TreeNode | null {
  const tokens = data.split(',');
  let i = 0;
  const build = (): TreeNode | null => {
    const token = tokens[i++];   // consume one token, advance
    if (token === NULL) return null;
    const node = new TreeNode(Number(token));
    node.left = build();         // left subtree consumes next tokens
    node.right = build();        // right subtree consumes what remains
    return node;
  };
  return build();
}

Reading it block by block

The sentinel. NULL = '#'is the marker for an absent child. Picking a value that can't appear as a real node (here a non-numeric character) keeps decoding unambiguous.

serialize → preorder dfs. A null node pushes # and returns. A real node pushes its value first, then recurses left and right. Emitting before descending is what makes the very first token the root.

Join into a string. out.join(',') turns the token list into the wire format. For the example tree you get 1,2,#,#,3,4,#,#,5,#,#.

deserialize → mirror recursion. Split back into tokens and keep one cursor i. build() consumes tokens[i++]: a # returns null; otherwise it makes a node and recursively builds left then right.

Why the cursor just works. build reads exactly one token before recursing, in the same order serialize wrote them. So the shared, advancing i walks the stream front-to-back and the call stack rebuilds the identical shape.

Complexity → Both directions are O(n) time — each node and each null marker is touched once. Space is O(n) for the serialized string plus O(h) recursion stack (h = tree height, up to O(n) when skewed).

INTERVIEWFollow-ups they'll ask

"Do it iteratively / with BFS instead?" A level-order (queue) encoding also works — enqueue children, write # for nulls; decode with a queue and a cursor over the tokens.
"What if it's a BST?" You can skip null markers entirely: preorder values plus value-range bounds during decode are enough to place every node uniquely.
"Node values contain commas or the delimiter?" Use a length-prefixed or escaped encoding (e.g. len#value) so the parser can't be fooled.
"Make it more compact?" Drop trailing #markers, pack into a binary format, or use BFS so leaves don't each cost two sentinels.
"Reconstruct from two traversals?" Preorder + inorder (or postorder + inorder) also pins down a unique tree — the same recursion-with-a-cursor idea.

OPTIMAL DFS

serializeTree.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const NULL = '#';

// Preorder DFS: node, then left, then right. '#' marks an absent child.
function serialize(root: TreeNode | null): string {
  const out: string[] = [];
  const dfs = (node: TreeNode | null): void => {
    if (node === null) {
      out.push(NULL);          // record the hole so shape survives
      return;
    }
    out.push(String(node.val)); // emit value BEFORE descending (preorder)
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  return out.join(',');
}

// Rebuild by consuming the same preorder stream front-to-back.
function deserialize(data: string): TreeNode | null {
  const tokens = data.split(',');
  let i = 0;
  const build = (): TreeNode | null => {
    const token = tokens[i++];   // consume one token, advance
    if (token === NULL) return null;
    const node = new TreeNode(Number(token));
    node.left = build();         // left subtree consumes next tokens
    node.right = build();        // right subtree consumes what remains
    return node;
  };
  return build();
}

ALT 1 BFS level-order (queue)

O(n) time · O(n) space

Encode the tree breadth-first with # for nulls — this is the familiar LeetCode array format, and a single queue wires children back up on decode.

approach-2.ts
const NULL = '#';

// Level-order: sweep the tree with a queue, writing every value and a
// '#' for each missing child, row by row.
function serialize(root: TreeNode | null): string {
  if (root === null) return NULL;
  const out: string[] = [];
  const queue: (TreeNode | null)[] = [root];
  while (queue.length > 0) {
    const node = queue.shift() as TreeNode | null;
    if (node === null) {
      out.push(NULL);            // record the hole; it has no children to enqueue
      continue;
    }
    out.push(String(node.val));  // emit value, then queue BOTH children (even nulls)
    queue.push(node.left);
    queue.push(node.right);
  }
  return out.join(',');
}

// Decode with a cursor over the tokens: the first token is the root, then
// each real node pulls its next two tokens as left/right children.
function deserialize(data: string): TreeNode | null {
  const tokens = data.split(',');
  if (tokens[0] === NULL) return null;
  const root = new TreeNode(Number(tokens[0]));
  const queue: TreeNode[] = [root];
  let i = 1;                              // tokens[0] already consumed as root
  while (queue.length > 0) {
    const node = queue.shift() as TreeNode;
    const leftTok = tokens[i++];          // next token is this node's left child
    if (leftTok !== NULL) {
      node.left = new TreeNode(Number(leftTok));
      queue.push(node.left);
    }
    const rightTok = tokens[i++];         // then its right child
    if (rightTok !== NULL) {
      node.right = new TreeNode(Number(rightTok));
      queue.push(node.right);
    }
  }
  return root;
}

Note → Numeric Number(tok) handles negatives for free, and the queue guarantees parent/child order matches the write order — so unbalanced trees round-trip exactly.

ALT 2 Postorder DFS (decode from the right)

O(n) time · O(n) space

Serialize as left, right, root — so the root lands last. Decoding then consumes the stream from the back, building the right child before the left.

approach-3.ts
const NULL = '#';

// Postorder: left subtree, then right subtree, then the node itself.
// The very last token is therefore the overall root.
function serialize(root: TreeNode | null): string {
  const out: string[] = [];
  const dfs = (node: TreeNode | null): void => {
    if (node === null) {
      out.push(NULL);            // mark the hole so shape survives
      return;
    }
    dfs(node.left);
    dfs(node.right);
    out.push(String(node.val));  // emit value AFTER both children (postorder)
  };
  dfs(root);
  return out.join(',');
}

// Mirror the postorder by consuming from the RIGHT end. Each node pops its
// own token first, then builds RIGHT before LEFT (reverse of write order).
function deserialize(data: string): TreeNode | null {
  const tokens = data.split(',');
  let i = tokens.length - 1;             // cursor walks backwards
  const build = (): TreeNode | null => {
    const token = tokens[i--];           // consume one token from the tail
    if (token === NULL) return null;
    const node = new TreeNode(Number(token));
    node.right = build();                // right was written last (before root) → read first
    node.left = build();                 // left was written before right → read second
    return node;
  };
  return build();
}

Note → The right-before-left order on decode is the exact reverse of the left-before-right write order; reading from the tail keeps the shared cursor in lockstep with the stream.

MNEMONIC The one-liner

"Preorder out with # for nulls; same recursion, one cursor, reads it back."

TRIGGERS When you see _ → reach for _

encode/decode a tree losslessly	preorder DFS + null sentinels
plain traversal is ambiguous	emit # for every missing child
rebuild from a token stream	shared cursor i, consume one per call
subtree identity / duplicate subtrees	use the serialization string as a key

SKELETON The reusable shape

skeleton.ts
const NULL = '#';
function serialize(root: TreeNode | null): string {
  const out: string[] = [];
  const dfs = (n: TreeNode | null) => {
    if (!n) { out.push(NULL); return; }
    out.push(String(n.val));
    dfs(n.left); dfs(n.right);
  };
  dfs(root);
  return out.join(',');
}
function deserialize(data: string): TreeNode | null {
  const t = data.split(','); let i = 0;
  const build = (): TreeNode | null => {
    const x = t[i++];
    if (x === NULL) return null;
    const node = new TreeNode(Number(x));
    node.left = build(); node.right = build();
    return node;
  };
  return build();
}

FLASHCARDS Tap to flip

Why must serialize emit a marker for null children?

Without #the value stream is ambiguous — you can't tell where a subtree ends, so the tree isn't recoverable.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Why does serialize emit "#" for null children?

QUESTION 02

In a preorder serialization, the first token is always:

QUESTION 03

How does deserialize keep its place in the token stream?

QUESTION 04

serialize for the tree 1,2,3,null,null,4,5 (preorder, # for nulls) is:

QUESTION 05

Time complexity of serialize on an n-node tree?

QUESTION 06

If node values could themselves contain the comma delimiter, the fix is to:

QUESTION 07

For a Binary Search Tree specifically, you can:

QUESTION 08

#297 · Serialize and Deserialize Binary TreeEncode any binary tree to a string and decode it back to the identical tree. A preorder DFS that emits a # sentinel for every null child makes the shape self-describing, so reading the tokens back front-to-back rebuilds it in one pass.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Null markers make a traversal reversible

RECIPE Emit value + nulls, then replay the recursion

COST Complexity & alternatives

Where the time goes

RUN IT Preorder out, preorder back in

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL DFS

ALT 1 BFS level-order (queue)

ALT 2 Postorder DFS (decode from the right)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _