Appearance
4.14.15 — Serialize and Deserialize Binary Tree
LeetCode 297 · Hard · ★ Blind 75
The problem
Write a tree to a string, and rebuild the identical tree from that string. The format is yours to choose.
1
/ \
2 3 → some string → the same tree back
/ \
4 5The pattern
4.14.13 needed two traversals to rebuild a tree, because one alone is ambiguous:
1 1
/ \
2 2Both give pre-order [1, 2].
But the ambiguity only exists because you cannot tell a missing left child from a missing right child. Write the missing children down and it disappears.
1 → 1, 2, #, #, # (1, then left=2 with two nulls, then right=null)
/
2
1 → 1, #, 2, #, # (1, then left=null, then right=2)
\
2One traversal is now enough. That is the whole idea, and it is the same insight as 4.4.6 Encode and Decode Strings: make the encoding self-describing and the decoder never has to guess.
Why pre-order
Pre-order writes the root first. So the decoder reads a value, creates that node, and then recursively builds its left subtree and its right subtree — consuming the string in exactly the order it was written. The reader needs no lookahead and no index arithmetic.
In-order would not work at all, because the decoder would not know which value is the root of the piece it is reading.
The solution
python
class Codec:
def serialize(self, root) -> str:
parts = []
def walk(node):
if not node:
parts.append('#')
return
parts.append(str(node.val))
walk(node.left)
walk(node.right)
walk(root)
return ','.join(parts)
def deserialize(self, data: str):
values = iter(data.split(','))
def build():
token = next(values)
if token == '#':
return None
node = TreeNode(int(token))
node.left = build() # order matters: left, then right
node.right = build()
return node
return build()ts
function serialize(root: TreeNode | null): string {
const parts: string[] = [];
(function walk(node: TreeNode | null) {
if (!node) { parts.push('#'); return; }
parts.push(String(node.val));
walk(node.left);
walk(node.right);
})(root);
return parts.join(',');
}
function deserialize(data: string): TreeNode | null {
const values = data.split(',');
let i = 0;
function build(): TreeNode | null {
const token = values[i++];
if (token === '#') return null;
const node = new TreeNode(Number(token));
node.left = build();
node.right = build();
return node;
}
return build();
}Every node writes exactly three things: its value, its left subtree, its right subtree. A null writes one thing. That regularity is what makes the decoder a mirror image of the encoder.
The iterator (or the index) must be shared across all recursive calls, because each call consumes tokens that the next one must not re-read. Python's iter gives this naturally; TypeScript uses a closure variable.
The comma matters. Joining with nothing would make 1 and 2 indistinguishable from 12. The same delimiter reasoning as 4.4.6 — except here the values are numbers and cannot contain a comma, so a plain separator is safe. If values could be arbitrary strings, you would need length prefixing instead.
Build left before right, matching the order they were written.
Trace
Serialising the example tree:
1, 2, #, #, 3, 4, #, #, 5, #, #Reading it back: take 1 → make a node → build its left. Take 2 → make a node → build its left, which reads # → null; build its right, which reads # → null. Return to node 1's right: take 3 → build its left, reading 4, #, #; build its right, reading 5, #, #. Done, and the input is exactly consumed.
Complexity
O(n) time both ways. The string has one token per node plus one per null child, and a tree with n nodes has exactly n+1 null slots, so the string holds 2n + 1 tokens.
O(n) space for the string, plus O(h) for the recursion.
The BFS alternative
You can serialise level by level instead, which is what LeetCode's own display format does:
[1, 2, 3, null, null, 4, 5]Deserialising uses a queue: take a node off, read the next two tokens as its children, and push any non-null children back on.
It is equally valid and produces a more human-readable string. Pre-order is usually easier to write under pressure because the encoder and decoder are mirror images, while the BFS version needs a queue on both sides.
Where this goes next
- Serialize and Deserialize BST (LeetCode 449) — a search tree needs no null markers at all, because the ordering already tells the decoder where each subtree ends. That produces a shorter string, and noticing why is a good test of whether you understand what the markers are for.
- Find Duplicate Subtrees — serialise every subtree and count identical strings in a hash map.
- Real systems — JSON, Protocol Buffers, and Python's
pickleall face this problem, and all of them solve it with self-description: either explicit markers or length prefixes. Chapter 10.4 covers serialisation formats properly.
The rule: a traversal plus explicit null markers determines a tree uniquely. Self-describing data needs no second traversal.
What the interviewer will push on
"Why is one traversal enough here when 4.14.13 needed two?" The null markers remove the ambiguity.
"Why pre-order and not in-order?" The decoder must know the root before it can build the subtrees.
"Why the separator?" Multi-digit values would run together.
"What if node values were arbitrary strings?" Delimiters stop being safe, so length-prefix each value, exactly as in 4.4.6.
"How much bigger is the string than the tree?" 2n + 1 tokens, since a tree with n nodes has n+1 empty child slots.
"Could you do it without null markers?" For a BST, yes — the ordering substitutes for them.
One thing to volunteer: say why the naive traversal is ambiguous, with the two-node example, before you propose the fix. The fix only sounds clever when the problem it solves has been named.
Next: 4.15 is short and specific — three problems built on the trie from Chapter 4.13.4, and one of them is where backtracking and tries meet.