Hard difficulty · Algorithm · Topics: tree, dfs, preorder, design, string
Serialization turns an in-memory tree into a flat string you can store or send; deserialization rebuilds an identical tree from that string. This sample's Codec writes a preorder traversal with explicit null markers for missing children, and reads it back with the same recursion. The roundTrip method builds a tree from a level-order array, serializes it, deserializes the string, and returns both the string and the rebuilt tree in level order, so you can check that nothing was lost.
A preorder list of values alone is ambiguous: 1,2,3 could be a chain or a root with two children. The fix is to also write down where the tree stops: every missing child becomes a null token. With those markers, the token stream describes exactly one tree.
Reading works because preorder is "node, then everything on its left, then everything on its right". The reader consumes one token for the node, then lets a recursive call consume exactly the tokens of the left subtree (it stops by itself at the matching null markers), and then another call consumes the right subtree. A single shared cursor pos is all the state needed.
serialize(root)
write(node): if node is null, append "null" and return.write(node.left), then write(node.right).deserialize(data)
tokens; set pos = 0.read(): take tokens[pos] and advance pos.
"null" → return null.node.left = read() and node.right = read().read() returns the root.roundTrip(values) = buildTree → serialize → deserialize → toLevelOrder (BFS with null for gaps, trailing nulls trimmed).
Case 0: values = [1, 2, 3, null, null, 4, 5].
1
/ \
2 3
/ \
4 5
serialize (preorder, one token per call):
write(1) -> "1"
write(2) -> "2"
write(null) -> "null" write(null) -> "null"
write(3) -> "3"
write(4) -> "4", "null", "null"
write(5) -> "5", "null", "null"
data = "1,2,null,null,3,4,null,null,5,null,null" (11 tokens = 5 nodes + 6 nulls)
deserialize (pos = index of the token being read):
pos 0 "1" new node 1, read its left
pos 1 "2" new node 2, read its left
pos 2 "null" 2.left = null
pos 3 "null" 2.right = null -> 2 is done, back to 1
pos 4 "3" 1.right = new node 3
pos 5 "4" 3.left = 4; pos 6, 7 are its null children
pos 8 "5" 3.right = 5; pos 9, 10 are its null children
toLevelOrder(copy) gives [1, 2, 3, null, null, 4, 5], identical to the input.
| Operation | Time | Space | Why |
|---|---|---|---|
| serialize | O(n) | O(n) | every node and every null child is written once (2n + 1 tokens) |
| deserialize | O(n) | O(n) | every token is read once; recursion depth O(h) |
| roundTrip | O(n) | O(n) | build + serialize + deserialize + BFS, each linear |
null markers: the shape becomes ambiguous and the rebuilt tree differs.pos.parseInt on "null" (gives NaN) instead of checking for the marker first.serialize, parts grows one token per call while node walks the tree in preorder.deserialize, pos moves through tokens and the rebuilt tree node grows; the call stack depth shows which subtree is being read.toLevelOrder fills queue and result breadth-first at the end.Input: values = [1, 2, 3, null, null, 4, 5]
Output: ["1,2,null,null,3,4,null,null,5,null,null", [1, 2, 3, null, null, 4, 5]]
[0, 10^4].-1000 <= Node.val <= 1000class Codec {
// Preorder with "null" markers, e.g. "1,2,null,null,3,null,null"
serialize(root) {
const parts = [];
function write(node) {
if (node === null) {
parts.push("null"); // marks a missing child so the shape is kept
return;
}
parts.push(String(node.val));
write(node.left);
write(node.right);
}
write(root);
return parts.join(",");
}
// Reads the tokens back in the same preorder
deserialize(data) {
const tokens = data.split(",");
let pos = 0; // next token to read
function read() {
const token = tokens[pos];
pos++;
if (token === "null") return null;
const node = new TreeNode(Number(token));
node.left = read();
node.right = read();
return node;
}
return read();
}
}
// Builds a tree, serializes it, rebuilds it, and returns [string, rebuilt tree in level order]
function roundTrip(values) {
const root = buildTree(values);
const codec = new Codec();
const data = codec.serialize(root);
const copy = codec.deserialize(data);
return [data, toLevelOrder(copy)];
}
// Builds TreeNodes from a LeetCode level-order array (null = missing child)
function buildTree(values) {
const nodes = values.map((v) => (v === null ? null : new TreeNode(v)));
let next = 1;
for (const node of nodes) {
if (node === null) continue;
if (next < nodes.length) node.left = nodes[next++];
if (next < nodes.length) node.right = nodes[next++];
}
return nodes.length > 0 ? nodes[0] : null;
}
// LeetCode level-order array of a tree, trailing nulls removed
function toLevelOrder(root) {
const result = [];
const queue = [root];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
if (node === null) {
result.push(null);
continue;
}
result.push(node.val);
queue.push(node.left, node.right);
}
while (result.length > 0 && result[result.length - 1] === null) result.pop();
return result;
}