Serialize and Deserialize Binary Tree
Serialize and Deserialize Binary Tree: encode a binary tree to a string and decode it back exactly.
- The number of nodes in the tree is in the range [0, 10⁴].
- -1000 <= Node.val <= 1000
Intuition
To serialize and deserialize binary tree structures, you need a string that can be turned back into the exact same tree — same values, same shape.
A plain preorder traversal is not enough. Preorder alone is ambiguous for a general binary tree: several different trees produce the same sequence, which is why the reconstruction problems always hand you two traversals.
The fix is to stop discarding the missing children. Write a marker where each null child would be, and the ambiguity disappears entirely:
- Preorder with explicit null markers encodes the shape as well as the values.
With the nulls present, every node's subtree boundaries are pinned down, because a null terminates a branch explicitly rather than leaving the reader to guess.
Deserialization then mirrors serialization exactly. Read tokens in the same preorder order: a marker produces null, anything else becomes a node whose left subtree is built from the following tokens, then its right. The recursion consumes tokens in precisely the order they were written, so a shared position pointer is all the bookkeeping needed.
Two practical details matter. Use a delimiter such as a comma so multi-digit and negative values survive the round trip, and pick a marker that can never be a value — # or null — since a bare -1 would be indistinguishable from real data.
To rebuild a tree from a flat string you need the null positions written down — that's the whole insight. Pre-order plus explicit null markers is self-delimiting: the first token is always the root, and recursion consumes exactly its own subtree before returning, so the boundary between left and right needs no separator. Without null markers you'd need two traversals to reconstruct, which is why in-order alone is never enough.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(n) space.
Serialize in preorder with null markers
Emit the node's value, then recurse left, then right, emitting a marker such as # at every null. The markers are what remove the ambiguity — without them, different trees serialize to identical strings.
Choose a delimiter and marker carefully
Join tokens with a comma so that 12 is not read as 1 and 2, and negatives survive intact. The null marker must be something no value can be — # is safe, a numeric sentinel is not.
Deserialize by consuming in the same order
Read tokens left to right. A marker returns null; any other token becomes a node whose left subtree is built from the tokens that follow, then its right. The write order and read order are identical, which is why no index arithmetic is needed.
Share one position across all calls
Use an iterator or a single mutable index so every recursive call consumes the next unread token. Passing a copy of the position would make each subtree re-read the same tokens and produce a wrong tree.
Consider BFS as the alternative
A level-order encoding with markers works equally well and is what LeetCode's own display format uses. It needs a queue instead of recursion and is worth mentioning, though preorder is usually the shorter code.
Cost of the round trip
Both directions visit every node and every null slot exactly once, giving O(n) time in each. The string holds n values plus n+1 markers, so it is O(n) in size, and recursion depth is O(h).
Solution & live demo
Common pitfalls
Omitting the null markers
def dfs(node):
if not node: return
out.append(str(node.val))
dfs(node.left); dfs(node.right)def dfs(node):
if not node:
out.append("#"); return
out.append(str(node.val))
dfs(node.left); dfs(node.right)"1,2" could be 2 as a left child or as a right child — the shape is unrecoverable. The # tokens are what encode structure; they're not padding.
Indexing the token list instead of consuming an iterator
tokens = data.split(",")
def build(i):
...
node.left = build(i + 1)
node.right = build(???)tokens = iter(data.split(","))
def build():
t = next(tokens)
...With an index you'd have to know how many tokens the left subtree swallowed before you could locate the right one — information you only get by rebuilding it. A shared iterator advances as a side effect, so by the time build() returns for the left child the cursor is already sitting on the right child's first token.
Rebuilding children inside the constructor call
return TreeNode(int(t), build(), build())
node = TreeNode(int(t)) node.left = build() node.right = build() return node
Argument evaluation order becomes load-bearing — in a language that evaluates right-to-left the subtrees come back swapped. Sequencing the two calls on their own lines makes the pre-order contract explicit.
Edge cases
Serializes to "#" and decodes to None.
Comma delimiting keeps tokens intact — never parse per character.