The catalog-pricing console from Level Order now has to snapshot the split tree, ship it across a restart, and rebuild the same questions. The intern reused that walk: values grouped by floor, missing children omitted. A full tree round-tripped. A left-only child came back sitting on the right — the string had lost the holes. A second intern dumped a heap-sized slot array; a spine filled millions of cells before the snapshot finished.
Serialize and deserialize must round-trip: same shape, same values. The binary tree post owns layout. The BFS post owns the FIFO ArrayDeque. Level Order is the same floor walk that drops nulls so a dashboard has no holes. Here we keep them: a "null" token in the string, never a null offered to the deque.
The problem
Design a codec: serialize turns a binary tree into a string; deserialize rebuilds a tree from that string. The pair is identity on structure and values. An empty tree is "null". A single node is that value plus two "null" children.
final class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}Sample trees. The string records every missing child of a live node. Level Order would return [[8], [3], [5]] for the second drawing and forget which side each child sat on.
8
/ \
3 10
/ \
9 14
→ 8,3,10,null,null,9,14,null,null,null,null
8
/
3
\
5
→ 8,3,null,null,5,null,null
(root = null) → null
[1] → 1,null,nullNote: Empty is the token "null", not an empty string. Use the same token for every hole. Comma-separated ints plus "null" is enough; this is not JSON.
A full heap-index array is the honest brute force
Allocate 2^(h+1)-1 slots, write a node at i, left at 2*i+1, right at 2*i+2, fill the rest with "null". Deserialize reads the same indices. Correct. A complete tree is dense. A spine of height h still pays Θ(2^h) cells.
String serializeHeap(TreeNode root) {
if (root == null) {
return "null";
}
int cap = (1 << (height(root) + 1)) - 1;
String[] slots = new String[cap];
Arrays.fill(slots, "null");
fill(root, 0, slots);
return String.join(",", slots);
}
void fill(TreeNode node, int i, String[] slots) {
if (node == null) {
return;
}
slots[i] = String.valueOf(node.val);
fill(node.left, 2 * i + 1, slots);
fill(node.right, 2 * i + 2, slots);
}
int height(TreeNode node) {
return node == null ? -1 : 1 + Math.max(height(node.left), height(node.right));
}At a dozen balanced nodes this is a rounding error. At a left spine of thirty questions you allocated a billion-slot string (1 << 30): encode the holes in the string, not a cell per cousin in a heap layout.
BFS, write null tokens, never offer null
Offer the root. While the queue is not empty, poll a live node, then for left and for right: if the child exists, append its value and offer it; if not, append "null" and do not offer. Children of a null are never considered — we never enqueued that null.
ArrayDeque refuses null. The holes live in the string, not on the deque.
q: [8] out: 8
poll 8 left 3 → offer 3 right null → token
q: [3] out: 8,3,null
poll 3 left null → token right 5 → offer 5
q: [5] out: 8,3,null,null,5
poll 5 left null right null
q: [] out: 8,3,null,null,5,null,nullDeserialize: if the string is "null", return null. Split on commas. The first token is the root; offer it. Then for each polled live node, consume the next two tokens as left and right: a "null" token leaves that child empty (do not offer); otherwise build the child, attach it, offer it.
The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack. Never offer null — holes are "null" tokens in the string.
String serialize(TreeNode root) {
if (root == null) {
return "null";
}
List<String> out = new ArrayList<>();
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
out.add(String.valueOf(root.val));
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node.left != null) {
out.add(String.valueOf(node.left.val));
q.offer(node.left);
} else {
out.add("null");
}
if (node.right != null) {
out.add(String.valueOf(node.right.val));
q.offer(node.right);
} else {
out.add("null");
}
}
return String.join(",", out);
}
TreeNode deserialize(String data) {
if (data.equals("null")) {
return null;
}
String[] tokens = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
int i = 1;
while (!q.isEmpty() && i < tokens.length) {
TreeNode node = q.poll();
if (!tokens[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(tokens[i]));
q.offer(node.left);
}
i++;
if (i < tokens.length && !tokens[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(tokens[i]));
q.offer(node.right);
}
i++;
}
return root;
}Time is O(n) — each live node is offered once, polled once, and writes two child tokens. Space is O(w) for the queue, w being the widest floor, plus O(n) for the string. A spine stays a thin queue and a linear string. Do not quote a graph seen set; there is nothing to mark.
Note: Return "null" for an empty root before you offer. Offering null throws on ArrayDeque. Increment i after a "null" token too — that slot is consumed even though nothing was attached.
What interviewers usually poke next
- Preorder with nulls.
val + "," + serialize(left) + "," + serialize(right), and"null"when the node is missing. A second codec, same round-trip, DFS frames instead of a queue. Same Tree already uses that dump as a brute compare. - Not JSON. Nested objects or a JSON array of nodes is a third encoding. The prompt is a string codec; comma tokens plus
"null"already round-trip. - Level Order. Same BFS, drops nulls, groups by floor. Different contract. Do not paste
[[8], [3], [5]]into this string.
You are done with this problem when you can walk 8,3,null,null,5,null,null out loud, rebuild the left-then-right-child tree, and say why the level-order lists cannot be the codec.