serialize
phase
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.
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.
#) 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.null node, append # and stop. These markers are what make the shape recoverable.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.# 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.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).
preorder (node → left → right), appending each value to the output. A # marks a missing child so the shape is recoverable.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();
}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.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.out.join(',') turns the token list into the wire format. For the example tree you get 1,2,#,#,3,4,#,#,5,#,#.i. build() consumes tokens[i++]: a # returns null; otherwise it makes a node and recursively builds left then right.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.# for nulls; decode with a queue and a cursor over the tokens.len#value) so the parser can't be fooled.#markers, pack into a binary format, or use BFS so leaves don't each cost two sentinels.| 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 |
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();
}#the value stream is ambiguous — you can't tell where a subtree ends, so the tree isn't recoverable.