Serialize and Deserialize Binary Tree

Serialization encodes a binary tree as a string; deserialization reconstructs the exact tree from that string. Implement a serialize and a deserialize so that deserialize(serialize(root)) returns a tree identical to the original.

Here you're given the root; return deserialize(serialize(root)) — the reconstructed tree, which the grader compares against the input. The tree is given/returned in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Encode empty children with a sentinel (like '#') so the structure is preserved.

A single preorder walk with null markers uniquely encodes the tree.

Deserialize by reading the tokens back in the same order the serializer wrote them.

Common doubts

Without them a single traversal is ambiguous; recording nulls restores exactly which children are present.

No — preorder or level-order both work, as long as serialize and deserialize use the same one.

It doesn't need to: it recursively consumes a node's entire left subtree, then its right, so token consumption self-delimits.

Interview follow-ups

· What an interviewer asks next.

A BST needs only preorder (no null markers) — the ordering property lets deserialize infer structure via value bounds.

Record each node's child count (or a group terminator) so deserialize knows how many children to read.

Fun facts

The null-marker preorder string is a complete, order-preserving fingerprint of a tree — equal strings mean identical trees.
This encoding is the basis of the 'subtree of another tree' trick: substring match on serialized forms.

Asked at

AmazonFacebookGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 2, 3, null, null, 4, 5]
Output: [1, 2, 3, null, null, 4, 5]
serialize then deserialize reproduces the same tree.

Example 2

Input: root = []
Output: []
An empty tree round-trips to empty.

Constraints

- The number of nodes is in the range [0, 10^4] - -1000 <= Node.val <= 1000

The whole trick is null markers. A traversal that also records the empty children uniquely encodes a tree — and reading that same stream back, markers and all, rebuilds it exactly. No second traversal needed, because the null markers restore the structure the inorder split would otherwise provide.

Prerequisites

Before you start

· Concepts used directly in the solution.

Traversal + markers. A preorder (or level-order) walk that writes a sentinel for each null child.

Stream parsing. Read the tokens back in the same order to rebuild.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Encoding

“How do you encode empty children?”

With a sentinel token (like #) so structure is preserved.

“Preorder or level-order?”

Either works, as long as serialize and deserialize agree.

The ideal opening — say it like this

I do a preorder walk and write a marker for every null, which uniquely encodes the tree.

To deserialize I read the same stream: a value creates a node whose left then right subtrees I build recursively; a marker returns null.

Understand the problem

Worked example — tree [1, 2, 3, null, null, 4, 5], preorder codec

serialize:  1,2,#,#,3,4,#,#,5,#,#
deserialize: 1 -> left(2 -> #,#) -> right(3 -> left(4 -> #,#), right(5 -> #,#))
reconstructed tree == original

Key observations

1Aha

Null markers make one traversal enough

Recording empty children restores the structure, so you don't need a second traversal.

2Aha

Serialize and deserialize must mirror each other

The reader consumes tokens in exactly the order the writer produced them.

3Aha

Preorder or level-order — pick one

Both are O(n); preorder is a clean recursion, level-order a clean queue loop.

Brute force vs optimal

	Level-order (BFS) codec	Preorder (DFS) codec
Idea	Queue; sentinel for null children	Recursion; sentinel for null children
Time	O(n)	O(n)
Space	O(n)	O(n)

Both preserve the tree exactly. Full code is in the Approaches selector below.

Summary

Key takeaway

Serialize with a traversal that writes a null-marker for every empty child; deserialize by reading the same stream back. Preorder or level-order, both O(n).

serialize(node):   if null: emit "#"; else emit val; serialize(left); serialize(right)
deserialize():     v = next; if v=="#": return null; node=v; node.left=deserialize(); node.right=deserialize()