LeetCode #297 Hard

Serialize and Deserialize Binary Tree

Encode a binary tree to a string and decode it back exactly.

treedfsdesign

02

Intuition

Preorder with explicit null markers is unambiguous: the nulls pin down where subtrees end, so the same recursion that wrote the string can replay it. Serialization is a preorder dump; deserialization is the mirror-image recursive read.

How to spot this pattern

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.

03

Approach

1

Serialize: preorder + '#' for null

dfs(node): emit val, recurse left, recurse right; emit # at nulls. Join with commas (handles multi-digit and negatives).

2

Deserialize: consume in the same order

Read the next token: '#' → None; else make the node and build left then right. An iterator carries the position implicitly.

3

Why it round-trips

Preorder with nulls encodes the exact shape — no inorder needed, unlike the classic two-traversal reconstruction.

04

Solution & live demo

▶1class Codec:
▶2    def serialize(self, root):
▶3        out = []
▶4        def dfs(node):
▶5            if not node:
▶6                out.append("#"); return
▶7            out.append(str(node.val))
▶8            dfs(node.left); dfs(node.right)
▶9        dfs(root)
▶10        return ",".join(out)
▶11 
▶12    def deserialize(self, data):
▶13        tokens = iter(data.split(","))
▶14        def build():
▶15            t = next(tokens)
▶16            if t == "#": return None
▶17            node = TreeNode(int(t))
▶18            node.left = build()
▶19            node.right = build()
▶20            return node
▶21        return build()

05

Common pitfalls

Omitting the null markers

✗ Wrong

def dfs(node):
    if not node: return
    out.append(str(node.val))
    dfs(node.left); dfs(node.right)

✓ 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

✗ Wrong

tokens = data.split(",")
def build(i):
    ...
    node.left = build(i + 1)
    node.right = build(???)

✓ Right

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

✗ Wrong

return TreeNode(int(t), build(), build())

✓ Right

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.

06

Edge cases

Empty tree

Serializes to "#" and decodes to None.

Negative / multi-digit values

Comma delimiting keeps tokens intact — never parse per character.

07

Complexity

Time

O(n)

Space

O(n)

One pass each way; string size O(n).